I was wondering whether the graph isomorphism problem had two facettes, and whether answering them would be different in terms of complexity.
The facettes are as follows:
- Determine that at least one isomorphism must exist, i.e., the graphs are isomorph
- Finding one specific isomorphism
The former asks to determine the existance of an isomorphism, while the latter asks to find a specific isomorphism.
Thanks, Alex
Suppose we have an oracle to solve the decision variant of Graph Isomorphism (GI).
Let $G, H$ be our input graphs. Start with vertex $v_{1} \in V(G)$. We search for a vertex $u_{1} \in V(H)$ such that there is an isomorphism sending $v_{1} \mapsto u_{1}$. This results in $n$ calls to the GI oracle.
We repeat this process on the graphs $G, H$, where we have labeled $v_{1} \mapsto u_{1}$, now selecting some vertex $v_{2} \in V(G)$. So now we search for a matching vertex $u_{2} \in V(H)$.
In total, we make $O(n^{2})$ queries to the GI oracle.
Mathon has a number of reductions from search and counting variants of GI to the decision variant: https://www.sciencedirect.com/science/article/pii/0020019079900048