1
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

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!

$\endgroup$
1
  • 1
    $\begingroup$ Thank you very much. In the time I was waiting for this answer I found precisely this reduction (with the same idea of using a clique). $\endgroup$ Oct 13 at 14:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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