Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:
- to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not
- for each notrivial automorphism of the group g, you add the constraint that the sum of the variables corresponding to the non-fixed points by g is at least 1 (which means that at least one non-fixed vertex belongs to the set you are looking for). (here i find the non-fixed points of g by looking to its cycle representation)
- then you ask a MILP solver to minimize the sum of all variables (which means that you want the set to be as small as possible)
Here is th code:
def determining_set(G):
p = MixedIntegerLinearProgram(maximization=False)
x = p.new_variable(binary=True)
for g in G.automorphism_group():
if not g.is_one():
p.add_constraint(sum(x[i] for i in flatten(g.cycle_tuples())) >= 1)
p.solve()
sol = p.get_values(x)
return [i for i in sol if sol[i] != 0]
Which you can test:
sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
You can learn more about the use of MILP on the thematic tutorial : http://doc.sagemath.org/html/en/thema...
I am not sure that removing the details you gave in your first edit makes the question clearer.