0

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:

  1. Determine that at least one isomorphism must exist, i.e., the graphs are isomorph
  2. 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

Alex
  • 23

1 Answers1

0

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

ml0105
  • 14,674