patternMinor
Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?
Viewed 0 times
determininggraphnonefficientalgorithmhastrivialautomorphismforthere
Problem
I'm working on a problem related to Latin squares, and I want a method for what essentially boils down to the decision problem:
Input: A finite, simple graph G.
Output:
Hence...
Question: Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?
We could use Nauty or Bliss (and possibly some other packages) to compute the whole automorphism group, but I don't need it; all I need to determine is whether or not it's trivial.
It's possible this decision problem is theoretically equivalent in complexity to "compute the whole automorphism group" in some way. I'm not sure.
For my purpose, "efficient" basically means "faster in practice than computing the whole automorphism group", but I'm also interested in the theory behind it.
Input: A finite, simple graph G.
Output:
YES if G has a non-trivial automorphism, NO otherwise.Hence...
Question: Is there an efficient algorithm for determining whether or not a graph has a non-trivial automorphism?
We could use Nauty or Bliss (and possibly some other packages) to compute the whole automorphism group, but I don't need it; all I need to determine is whether or not it's trivial.
It's possible this decision problem is theoretically equivalent in complexity to "compute the whole automorphism group" in some way. I'm not sure.
For my purpose, "efficient" basically means "faster in practice than computing the whole automorphism group", but I'm also interested in the theory behind it.
Solution
Since you are also interested in the theory behind it, I would give you a quasi-polynomial time algorithm for your problem.
For each pair of vertices $u\neq v$ (of same degree) in $G$, we try to see if it it possible to swap $u$ and $v$.
To do this, make a copy of $G$, call it $G'$. Now, delete $u$ from $G$, delete (copy of) $v$ from $G'$.
Then, for each $w\in N(u)$ attach to it a very long path, but only polynomially long.
Then, for each (copy of) $w\in N(copy\ of\ v)$ attach to it a very long path, but only polynomially long.
All the mentioned above very long path, but polynomially long, should be of the same length.
Call Babai's algorithm on the input of this newly produced pair of graphs.
If for any pair $(u, v)$, we have a $YES$ answer from Babai's, answer $YES$ and halt.
If none returns a $YES$ answer, answer $NO$ and halt.
Clearly, attaching to all vertices in $N(u)$ and $N(v)$ forces the graph isomorphism of Babai's inner working mechanism of his algorithm to only map vertices in $N(u)$ to $N(v)$. Thus, if Babai's answer is $YES$ then we can safely plug in back $u$ and $v$ to have a non-trivial automorphism of $G$, since $G'$ is a copy of $G$.
The run-time complexity is still quasi-poly.
For each pair of vertices $u\neq v$ (of same degree) in $G$, we try to see if it it possible to swap $u$ and $v$.
To do this, make a copy of $G$, call it $G'$. Now, delete $u$ from $G$, delete (copy of) $v$ from $G'$.
Then, for each $w\in N(u)$ attach to it a very long path, but only polynomially long.
Then, for each (copy of) $w\in N(copy\ of\ v)$ attach to it a very long path, but only polynomially long.
All the mentioned above very long path, but polynomially long, should be of the same length.
Call Babai's algorithm on the input of this newly produced pair of graphs.
If for any pair $(u, v)$, we have a $YES$ answer from Babai's, answer $YES$ and halt.
If none returns a $YES$ answer, answer $NO$ and halt.
Clearly, attaching to all vertices in $N(u)$ and $N(v)$ forces the graph isomorphism of Babai's inner working mechanism of his algorithm to only map vertices in $N(u)$ to $N(v)$. Thus, if Babai's answer is $YES$ then we can safely plug in back $u$ and $v$ to have a non-trivial automorphism of $G$, since $G'$ is a copy of $G$.
The run-time complexity is still quasi-poly.
Context
StackExchange Computer Science Q#87599, answer score: 2
Revisions (0)
No revisions yet.