Graph Isomorphism Problem: decisional vs functional

Question

The Graph Isomorphism Problem is a classic in Computer Science.

In its decision version $(DGI)$, we are given two graphs $G$ and $H$ and we are asked if there exists an isomorphism between the two. In its function version $(FGI)$, we want to produce in output the found isomorphism (if it exists).

It is a (in)famous open problem whether $DGI$ is either in $P$, is $NP$-complete or belongs to the $NP$-intermediate class.

My question is: what do we know about its function version? Is it (polynomially) equivalent to its decision version? Clearly, $DGI \preceq_P FGI$. What about the other direction?

Thank you.

Answer 1

Yes $FGI \preceq_P DGI$ also holds. Assume you have a black box $B$ that solves $DGI$ in polynomial time. You can easily solve $FGI$ in deterministic polynomial time with polynomial many calls to $B$.

First let $K_n$ be a clique on $n$ vertices. Let us define the function addClique(G, v, n) that adds to a graph $G$ a copy of $K_n$, and makes one of its vertices adjacent to $v$ in $G$. It returns a set $S$ of the vertices of the clique. We define remove(G, S) that removes a set of $n$ vertices $S$ from a graph $G$. Clearly such functions can be implemented in polynomial time in the size of $G$ and $n$.

Given two graphs $G_1, G_2$. Fix an ordering $v_1, \dots v_n$ of the vertices of $G_1$, and $w_1, \dots w_n$ for $G_2$. The algorithm goes as follows:

iso[n] = [0,.., 0]
If not B(G1, G2):
   Return false
For each vertex vi, i in [n]:
   addClique(G1, vi, n+i)
   For each vertex uj, j in [n]:
      if iso[j] != 0:
         continue
      iso[j] = i
      S = addClique(G2, uj, n+i)
      if B(G1, G2):
         break
      iso[j] = 0
      remove(G2, S)
 

We claim that if an isomorphism exists, then this algorithm finds one, where $u_j$ is assigned to $v_{iso[j]}$. The correctness follows from the fact, that each copy of $K_n$ in $G_2$ can only be assigned to a unique well-defined copy of $K_n$ in $G_1$. The polynomial bound follows from the fact that we add at most $n$ cliques of size at most $2n$ to each of the graphs.

Try to prove these claims as a homework!