# Graph Isomorphism Problem: decisional vs functional

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.

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]:
For each vertex uj, j in [n]:
if iso[j] != 0:
continue
iso[j] = i

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.