<p>More specific to Babai's algorithm: yes, the algorithm not only finds an isomorphism, it finds generators of the automorphism group (and therefore effectively finds all isomorphisms) as part of the algorithm, that is, without the reduction of domotorp's answer.</p>

<p>In terms of deciding existence of an isomorphism (resp., unknotting) vs actually finding one, the keyword to search for is "search vs decision" or a "search to decision reduction" ("reducing search to decision" etc.). Such a reduction is known for graph isomorphism, as well as for NP-complete problems, but is an open question for more algebraic structures such as groups, and, I believe, knots, precisely because we don't know how to add "gadgets" as in domotorp's answer. </p>

CC BY-SA 3.0
2017-12-25T22:53:20.660Z
2017-12-25T22:53:20.660Z
Joshua Grochow
<p>These problems are polynomially equivalent.
Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are.
Attach a clique of size $n+1$ to an arbitrary vertex of each graph.
Test whether the resulting graphs are isomorphic or not.
If they are, then we can conclude that there's an isomorphism that maps the respective vertices to each other, thus we can delete them.
By repeating this test $n$ times, we can find (a possible) image for any vertex.
After this, we attach another clique, this time of size $n+2$ to a (different) arbitrary vertex of each original graph, and proceed as before, etc.
Eventually, we'll end up with two graphs that are isomorphic, with cliques of size $n+1,\ldots n+n$ hanging from their vertices, which makes the isomorphism unique.</p>

CC BY-SA 3.0
2017-12-24T21:24:57.670Z
Thanks!  Would similar gadgets work to show the set of Reidemeister moves relating two knots to each other, given only that they are equivaelnt to each other, or is this not known?
Mark S
CC BY-SA 3.0
2017-12-24T22:07:49.267Z
I doubt, as in that case I see no way of "ruining" a possible solution.
domotorp
CC BY-SA 3.0
2017-12-24T20:43:53.787Z
2017-12-25T20:48:30.913Z
2017-12-25T20:48:30.913Z
domotorp
<p>I have a (hopefully simple, maybe dumb) question on Babai's landmark <a href="https://arxiv.org/abs/1512.03547" rel="noreferrer">paper</a> showing that $\mathsf{GI}$ is quasipolynomial.</p>

<p>Babai showed how to produce a certificate that two graphs $G_i=(V_i,E_i)$ for $i\in\{1,2\}$ are isomorphic, in time quasipolynomial in $v=|V_i|$.</p>

<blockquote>
  <p>Did Babai actually show <em>how</em> to find an element $\pi\in S_v$ that permutes the vertices of $G_1$ to $G_2$, or is the certificate merely an existence-statement?</p>
</blockquote>

<p>If an oracle tells me that $G_1$ and $G_2$ are isomorphic, do I still need to look through all $v!$ permutations of the vertices?</p>

<p>I ask because I also think about knot equivalence.  As far as I know, it's not known to be, but say detecting the unknot were in $\mathsf{P}$.  Actually finding a sequence of Reidemeister moves that untie the knot might still take exponential time...</p>

<graph-isomorphism><search-problem>
Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?
Mark S
# Does Babai's quasipolynomial time $\mathsf{GI}$ algorithm actually generate the isomorphism?

(Asked by: username_0 on 2017-12-24)

I have a (hopefully simple, maybe dumb) question on Babai's landmark [paper](https://arxiv.org/abs/1512.03547) showing that $\mathsf{GI}$ is quasipolynomial.

Babai showed how to produce a certificate that two graphs $G\_i=(V\_i,E\_i)$ for $i\in\{1,2\}$ are isomorphic, in time quasipolynomial in $v=|V\_i|$.

> Did Babai actually show *how* to find an element $\pi\in S\_v$ that permutes the vertices of $G\_1$ to $G\_2$, or is the certificate merely an existence-statement?

If an oracle tells me that $G\_1$ and $G\_2$ are isomorphic, do I still need to look through all $v!$ permutations of the vertices?

I ask because I also think about knot equivalence. As far as I know, it's not known to be, but say detecting the unknot were in $\mathsf{P}$. Actually finding a sequence of Reidemeister moves that untie the knot might still take exponential time...

**Tags:** graph-isomorphism, search-problem


---

## 2 answers

### Answer by username_2 on 2017-12-24. Score: 28 | Accepted answer

These problems are polynomially equivalent.
Indeed, suppose that you have an algorithm that can decide whether two graphs are isomorphic or not, and it claims that they are.
Attach a clique of size $n+1$ to an arbitrary vertex of each graph.
Test whether the resulting graphs are isomorphic or not.
If they are, then we can conclude that there's an isomorphism that maps the respective vertices to each other, thus we can delete them.
By repeating this test $n$ times, we can find (a possible) image for any vertex.
After this, we attach another clique, this time of size $n+2$ to a (different) arbitrary vertex of each original graph, and proceed as before, etc.
Eventually, we'll end up with two graphs that are isomorphic, with cliques of size $n+1,\ldots n+n$ hanging from their vertices, which makes the isomorphism unique.

> **Comments:**
> **username_0**: Thanks!  Would similar gadgets work to show the set of Reidemeister moves relating two knots to each other, given only that they are equivaelnt to each other, or is this not known?  
> **username_2**: I doubt, as in that case I see no way of "ruining" a possible solution.  

---

### Answer by username_1 on 2017-12-25. Score: 17

More specific to Babai's algorithm: yes, the algorithm not only finds an isomorphism, it finds generators of the automorphism group (and therefore effectively finds all isomorphisms) as part of the algorithm, that is, without the reduction of username_2's answer.

In terms of deciding existence of an isomorphism (resp., unknotting) vs actually finding one, the keyword to search for is "search vs decision" or a "search to decision reduction" ("reducing search to decision" etc.). Such a reduction is known for graph isomorphism, as well as for NP-complete problems, but is an open question for more algebraic structures such as groups, and, I believe, knots, precisely because we don't know how to add "gadgets" as in username_2's answer.


---

