How can I compute the minimal fixing set?

Having the automorphism group Aut(G) of graph G, what is the minimal set of nodes S where each automporphism in Aut(G) contains at least one of the nodes in a set S?

For small graphs it could be computed without using Sage or any other programming. However, for large graphs, writing a piece of code is necessary.

edit retag close merge delete

I am not sure that removing the details you gave in your first edit makes the question clearer.

Sort by » oldest newest most voted

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)



more

The code works for small graphs but for large graph (200 nodes) it couldn't find the solution after one day. Could you modify the code so it sweep over the generators instead of automorphiosms. For example, having a set of generators like

gens=[(14,15), (13,14), (12,13), (9,11), (7,12), (6,7), (5,9), (4,10)(197,224)(198,225)(199,226)(202,229)(204,231)(205,232)(206,233)(218,245)(219,246), (3,5), (2,8)]

could you modify the code so that we can feed in the generators to the code and find the set S by sweeping on generators instead of automorphisms?

If you want to run over the generators only, you can replace the line

for g in G.automorphism_group():


with

for g in G.automorphism_group().gens():


But this trick will not lead to a correct result since a vertex that is non-fixed by both g1 and g2 can be fixed by g1*g2 even if g1*g2 is not the identity.

yes, you are right. Do you have any idea how we could speed up the algorithm to find S for a large set of automorphisms?

I have to think further. Could you please provide a construction of the graph you want the problem to be solved ? This seems to be a hard problem in general, so maybe we could fin something from the particular structure of the graph you want to study.