13
$\begingroup$

I have a (hopefully simple, maybe dumb) question on Babai's landmark paper 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...

Improve this question
$\endgroup$

2 Answers 2

Reset to default
28
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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? $\endgroup$
    – Mark S
    Dec 24, 2017 at 21:24
  • 3
    $\begingroup$ I doubt, as in that case I see no way of "ruining" a possible solution. $\endgroup$
    – domotorp
    Dec 24, 2017 at 22:07
17
$\begingroup$

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.

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.

Improve this answer
$\endgroup$

Your Answer

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

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