Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones

André Große, Jörg Rothe, Gerd Wechsung

TL;DR

If you have a "magic box" that can give you just a single correct piece of a complex puzzle, can you use it to solve the entire thing? This paper proves that for the Graph Isomorphism problem, knowing even one pair of vertices that map to each other is enough to reconstruct the entire isomorphism efficiently. It also extends this logic to finding Hamiltonian cycles, showing that a single edge can lead to a full path under certain conditions.

What Problem Does This Paper Address?

In computational complexity, there is a classic distinction between decision problems (Is there a solution?) and search problems (Find the solution). For many problems in the class NP, like Graph Isomorphism (GI), we know that if we can decide the problem, we can also find the solution through a process called "self-reducibility."

However, this paper looks at a more nuanced middle ground: partial search. Specifically, if an algorithm (or "oracle") can only give us a tiny fraction of a solution—say, just one vertex mapping out of a hundred—is that enough to find the rest?

Previous work by Gàl et al. (1999) showed that for Graph Isomorphism, you could find the whole solution if you were given a "small fraction" (roughly logarithmic) of the vertex mappings. The authors of this paper set out to prove that this requirement can be pushed to the absolute limit: a single pair of vertices is sufficient.

Methods

The authors propose a recursive algorithm that takes two isomorphic graphs ($G$ and $H$) and a "partial oracle." This oracle is a function that, when given two isomorphic graphs, returns exactly one pair of vertices $(x, y)$ such that some isomorphism maps $x$ to $y$.

The core challenge is that simply deleting the pair $(x, y)$ and recursing doesn't work. Deleting vertices can create new symmetries in the remaining subgraphs that weren't there before, potentially leading the oracle to return a pair that belongs to a "dead-end" isomorphism—one that cannot be extended to the original full graphs.

To solve this, the authors use a clique-attachment technique:

  1. When a vertex pair is identified, instead of just deleting it, the algorithm attaches unique "tags" to all its neighbors.
  2. These tags are cliques (fully connected subgraphs) of specific, increasing sizes.
  3. Because isomorphisms must preserve the size of these cliques, the "tags" force the oracle to stay consistent with the original global structure even as the graphs are modified.

The algorithm for Hamiltonian cycles follows a similar recursive structure but requires a "left-right-context" to ensure that the edges returned by the oracle can actually be linked together into a single continuous cycle.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets or benchmarks. The proofs are mathematical and apply to the general classes of all undirected simple graphs (for GI) and multigraphs (for Hamiltonian cycles).

Key Insights and Ideas

  • Optimal Improvement: The jump from needing $O(\log n)$ pieces of information to just $O(1)$ is an "optimal improvement." You cannot solve a search problem with zero pieces of information unless P = NP (or the specific problem is in P).
  • The Power of Self-Reducibility: The authors demonstrate that the inherent structure of the Graph Isomorphism problem—the fact that it can be broken down into smaller, similar sub-problems—is exactly what allows a single "hint" to be magnified into a full solution.
  • Symmetry Breaking: The "aha moment" is the realization that we can use cliques to "break" the symmetries of a graph. By artificially making vertices unique based on their relationship to previously found solution parts, we prevent the search from wandering into inconsistent branches.

Key Results

  • Theorem 2.2 (Graph Isomorphism): The authors prove that a recursive procedure can construct a complete isomorphism in polynomial time (specifically cubic time, $O(n^3)$) using an oracle that provides only a single vertex pair.
  • Theorem 3.2 (Hamiltonian Cycles): They establish a similar result for finding Hamiltonian cycles. If an oracle provides one edge that belongs to a cycle consistent with a specific "context" (the edges already chosen), the full cycle can be recovered in polynomial time.
  • Complexity: The GI algorithm is shown to be highly efficient, terminating after exactly $n$ loops (where $n$ is the number of vertices).

Limitations and Future Work

The result for Hamiltonian cycles is acknowledged as "slightly weaker" than the result for Graph Isomorphism. This is because the Hamiltonian oracle requires a "left-right-context"—essentially, the oracle needs to know which edges have already been picked to ensure the next edge it provides is compatible.

The authors leave an open question: Is this context actually necessary? Could we find a full Hamiltonian cycle using an oracle that returns any edge belonging to any Hamiltonian cycle, without any additional context? They also suggest that similar "partial-to-complete" reductions might exist for other hard NP problems, which remains a fertile ground for future research.

Summary updated

Abstract

We prove that computing a single pair of vertices that are mapped onto each other by an isomorphism φ between two isomorphic graphs is as hard as computing φ itself. This result optimally improves upon a result of Gál, Halevi, Lipton, and Petrank. We establish a similar, albeit slightly weaker, result about computing complete Hamiltonian cycles of a graph from partial Hamiltonian cycles.
BibTeX
@inproceedings{groe2002computing,
  author = {André Große and Jörg Rothe and Gerd Wechsung},
  title = {{Computing Complete Graph Isomorphisms and Hamiltonian Cycles from Partial Ones}},
  booktitle = {Theory Comput. Syst},
  year = {2002},
  url = {https://openreview.net/forum?id=uJ8fM1Gllk},
}

Loading related content...

Figure