1 | initial version |

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

2 | No.2 Revision |

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

Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.