ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Tue, 28 Aug 2018 04:02:33 -0500How can I compute the minimal fixing set?http://ask.sagemath.org/question/43433/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.Tue, 21 Aug 2018 06:01:42 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/Comment by tmonteil for <p>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?</p>
<p>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.</p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43453#post-id-43453I am not sure that removing the details you gave in your first edit makes the question clearer.Thu, 23 Aug 2018 14:20:48 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43453#post-id-43453Answer by tmonteil for <p>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?</p>
<p>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.</p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?answer=43443#post-id-43443Here 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/thematic_tutorials/linear_programming.htmlWed, 22 Aug 2018 10:08:45 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?answer=43443#post-id-43443Comment by ASH for <p>Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:</p>
<ul>
<li>to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not</li>
<li>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)</li>
<li>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)</li>
</ul>
<p>Here is th code:</p>
<pre><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]
</code></pre>
<p>Which you can test:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
</code></pre>
<p>You can learn more about the use of MILP on the thematic tutorial : <a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">http://doc.sagemath.org/html/en/thema...</a></p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43497#post-id-43497@tmonteil, I guess the MILP solver tries to find the solution via some iterations. Could we stop the code after some iterations (for example after 5 hours) and see the returned minimal solution?Tue, 28 Aug 2018 04:02:33 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43497#post-id-43497Comment by ASH for <p>Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:</p>
<ul>
<li>to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not</li>
<li>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)</li>
<li>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)</li>
</ul>
<p>Here is th code:</p>
<pre><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]
</code></pre>
<p>Which you can test:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
</code></pre>
<p>You can learn more about the use of MILP on the thematic tutorial : <a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">http://doc.sagemath.org/html/en/thema...</a></p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43464#post-id-43464Below is a link to download the graph structure.
http://uupload.ir/filelink/URYW8VJ1c3Ss/8ozt_274nodes.rar
It is a 274 node graph with 28311552 automorphisms. This is one of the smallest graphs I am working on.Fri, 24 Aug 2018 21:53:09 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43464#post-id-43464Comment by tmonteil for <p>Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:</p>
<ul>
<li>to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not</li>
<li>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)</li>
<li>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)</li>
</ul>
<p>Here is th code:</p>
<pre><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]
</code></pre>
<p>Which you can test:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
</code></pre>
<p>You can learn more about the use of MILP on the thematic tutorial : <a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">http://doc.sagemath.org/html/en/thema...</a></p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43458#post-id-43458I 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.Fri, 24 Aug 2018 08:21:14 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43458#post-id-43458Comment by ASH for <p>Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:</p>
<ul>
<li>to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not</li>
<li>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)</li>
<li>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)</li>
</ul>
<p>Here is th code:</p>
<pre><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]
</code></pre>
<p>Which you can test:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
</code></pre>
<p>You can learn more about the use of MILP on the thematic tutorial : <a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">http://doc.sagemath.org/html/en/thema...</a></p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43457#post-id-43457yes, you are right. Do you have any idea how we could speed up the algorithm to find S for a large set of automorphisms?Fri, 24 Aug 2018 04:18:57 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43457#post-id-43457Comment by tmonteil for <p>Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:</p>
<ul>
<li>to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not</li>
<li>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)</li>
<li>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)</li>
</ul>
<p>Here is th code:</p>
<pre><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]
</code></pre>
<p>Which you can test:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
</code></pre>
<p>You can learn more about the use of MILP on the thematic tutorial : <a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">http://doc.sagemath.org/html/en/thema...</a></p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43456#post-id-43456If 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.Fri, 24 Aug 2018 03:55:40 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43456#post-id-43456Comment by ASH for <p>Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:</p>
<ul>
<li>to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not</li>
<li>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)</li>
<li>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)</li>
</ul>
<p>Here is th code:</p>
<pre><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]
</code></pre>
<p>Which you can test:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
</code></pre>
<p>You can learn more about the use of MILP on the thematic tutorial : <a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">http://doc.sagemath.org/html/en/thema...</a></p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43455#post-id-43455The 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?Thu, 23 Aug 2018 23:04:51 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43455#post-id-43455Comment by ASH for <p>Here is a generic way to solve such problems (without understanding the fine structure of the objects). You create an integer program as follows:</p>
<ul>
<li>to each vertex of the graph, you assign a binary variable which tells whether the vertex belongs to your set or not</li>
<li>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)</li>
<li>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)</li>
</ul>
<p>Here is th code:</p>
<pre><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]
</code></pre>
<p>Which you can test:</p>
<pre><code>sage: G = graphs.PetersenGraph()
sage: determining_set(G)
[3, 4, 7]
sage: G = graphs.LollipopGraph(3,5)
sage: determining_set(G)
[0]
</code></pre>
<p>You can learn more about the use of MILP on the thematic tutorial : <a href="http://doc.sagemath.org/html/en/thematic_tutorials/linear_programming.html">http://doc.sagemath.org/html/en/thema...</a></p>
http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43449#post-id-43449Thanks a lot for your time. It works perfectly.Wed, 22 Aug 2018 21:35:23 -0500http://ask.sagemath.org/question/43433/how-can-i-compute-the-minimal-fixing-set/?comment=43449#post-id-43449