Abstract
This paper addresses the relationship between partial and complete solutions for hard search problems. We prove that computing a single pair of vertices mapped onto each other by an isomorphism $\phi$ between two isomorphic graphs is as hard as computing $\phi$ itself. This result optimally improves upon previous work by Gàl et al. which required logarithmic information. We establish a similar, albeit slightly weaker, result for computing complete Hamiltonian cycles from partial ones under specific contextual conditions.
Introduction: From Partial to Complete Solutions
In computational complexity, a fundamental question is whether finding a solution is significantly harder than deciding if one exists. For many problems in the class NP, "self-reducibility" allows us to bridge this gap. However, a more challenging scenario arises when we only have access to a "partial oracle"—a tool that provides only a tiny fragment of a solution, such as a single vertex mapping out of a hundred.
Previous research by Gàl et al. (1999) established that for Graph Isomorphism (GI), a complete mapping could be reconstructed if an oracle provided $O(\log n)$ vertex pairs. This paper pushes that boundary to the theoretical limit, demonstrating that a single pair ($O(1)$ information) is sufficient to reconstruct the entire isomorphism efficiently.
The Graph Isomorphism Reduction
The primary challenge in using a single vertex mapping $(x, y)$ to find the rest of the isomorphism is the risk of "dead ends." Simply removing the identified vertices and recursing can introduce new symmetries in the remaining subgraphs, potentially causing the oracle to return mappings that belong to an isomorphism inconsistent with the original global structure.
The Clique-Attachment Technique
To maintain global consistency, the authors introduce a symmetry-breaking method using clique attachments. When a vertex pair is identified, the algorithm does not delete it. Instead, it attaches unique "tags"—cliques of strictly increasing sizes—to the neighbors of the identified vertices.
Because any valid isomorphism must preserve the size of these cliques, these tags force the oracle to remain consistent with the original structure even as the graphs are modified. The algorithm proceeds recursively:
- Query the oracle for a single pair $(x, y)$.
- Attach a unique clique to $x$ in $G$ and $y$ in $H$.
- Repeat until all vertices are uniquely identified.
The authors prove in Theorem 2.2 that this procedure constructs a complete isomorphism in polynomial time (specifically $O(n^3)$), effectively showing that finding one pair is as hard as finding them all.
Hamiltonian Cycles and Contextual Oracles
The paper extends this logic to the Hamiltonian cycle problem. Here, the goal is to find a cycle that visits every vertex exactly once. The authors show that a partial oracle returning a single edge belonging to a Hamiltonian cycle can be used to find the entire cycle.
However, this result is slightly weaker than the GI result. The Hamiltonian oracle requires a "left-right-context"—it needs to know which edges have already been selected to ensure the next edge it provides is compatible with forming a single continuous path. Without this context, an oracle might return edges belonging to different, disjoint cycles, making it impossible to stitch them together into one Hamiltonian cycle.
Conclusion and Future Directions
The findings represent an optimal improvement in the study of partial search for Graph Isomorphism. By demonstrating that $O(1)$ information is sufficient for reconstruction, the authors highlight the powerful structural properties of GI. Key results include the polynomial-time reduction of GI search to partial GI search and a similar reduction for Hamiltonian cycles using contextual oracles. Future work remains to determine if the "context" requirement for Hamiltonian cycles can be removed, and whether similar "one-hint" reductions exist for other NP-complete problems.
Summary updated