Revision history [back]

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

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/thematic_tutorials/linear_programming.html

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]]
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/thematic_tutorials/linear_programming.html