9
$\begingroup$

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

Improve this question
$\endgroup$
6
  • $\begingroup$ This is equivalent to graph isomorphism. $\endgroup$
    – Yuval Filmus
    Commented Feb 1, 2018 at 12:57
  • 3
    $\begingroup$ @YuvalFilmus As far as I'm aware, there's no known reduction from "Is $G_1$ isomorphic to $G_2$" to "Does $G$ have a nontrivial automorphism." Obviously, if $G_1\simeq G_2$ then their disjoint union has a nontrivial automorphism (swap $G_1$ and $G_2$) but any nontrivial automorphism of $G_1$ would also be a nontrivial automorphism of $G_1+G_2$. $\endgroup$
    – David Richerby
    Commented Feb 1, 2018 at 14:37
  • $\begingroup$ Regarding your last question, if given an oracle to GA one can, in polynomial time, find a generating set of the automorphism group, then GI is Turing reducible to GA, which I am not sure is known. $\endgroup$
    – Ariel
    Commented Feb 1, 2018 at 15:55
  • $\begingroup$ @DavidRicherby What about the following paper? sciencedirect.com/science/article/pii/… $\endgroup$
    – Yuval Filmus
    Commented Feb 2, 2018 at 15:53
  • $\begingroup$ @YuvalFilmus OK, so you're using Turing reductions and I'm using many-one reductions. And I guess Turing reductions are more relevant to somebody who's actually trying to solve the problem. $\endgroup$
    – David Richerby
    Commented Feb 2, 2018 at 16:31

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.