Ask Your Question
1

How can I compute the minimal fixing set?

asked 2018-08-21 13:01:42 +0100

ASH gravatar image

updated 2023-05-19 14:35:14 +0100

FrédéricC gravatar image

Having the automorphism group Aut(G) of graph G, what is the minimal set of nodes S where each automorphism 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 flag offensive close merge delete

Comments

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

tmonteil gravatar imagetmonteil ( 2018-08-23 21:20:48 +0100 )edit

1 Answer

Sort by » oldest newest most voted
1

answered 2018-08-22 17:08:45 +0100

tmonteil gravatar image

updated 2018-08-22 17:09:27 +0100

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...

edit flag offensive delete link more

Comments

Thanks a lot for your time. It works perfectly.

ASH gravatar imageASH ( 2018-08-23 04:35:23 +0100 )edit

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?

ASH gravatar imageASH ( 2018-08-24 06:04:51 +0100 )edit

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.

tmonteil gravatar imagetmonteil ( 2018-08-24 10:55:40 +0100 )edit

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?

ASH gravatar imageASH ( 2018-08-24 11:18:57 +0100 )edit

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.

tmonteil gravatar imagetmonteil ( 2018-08-24 15:21:14 +0100 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-08-21 13:01:42 +0100

Seen: 381 times

Last updated: May 19 '23