Deciding if an undirected graph has a Hamilton circuit is a well-known NP-complete problem. Let’s consider the following problem :
ANOTHER HAMILTON CIRCUIT : Given a Hamilton circuit in a graph find another hamilton circuit.
It is easy to see that ANOTHER HAMILTON CIRCUIT is FNP-complete. What if we are given a Hamilton graph which is guaranteed to have a second Hamilton circuit. Following is a simple exercise :
Smith’s Theorem : Prove that if a cubic graph has a hamilton circuit then it must have a second one
Now consider the following computational poblem :
SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.
Thomason’s proof [Thomason’78] of Smith’s theorem yields an algorithm that given one Hamiltonian cycle in a cubic graph, computes another one. Since the second hamilton circuit is guaranteed to exist, SMITH belongs to complexity class TFNP. Note that TFNP is a semantic class. In a beautiful paper [Papadimitriou’94] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Infact one can convert Thomason’s proof into a PPA-membership proof of SMITH. Simply put, PPA is the undirected version of the complexity class PPAD. Krawczyk showed that [Krawczyk’99] the “PPA-graph” of SMITH can have exponentially long paths, thus proving that Thomason’s algorithm is exponential in the worst case.
- Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.
- Are there special cases of SMITH solvable in polynomial-time ?
- [Krawczyk’99] Adam Krawczyk: The Complexity of Finding a Second Hmiltonian Cycle in Cubic Graphs. J. Comput. Syst. Sci. 58(3): 641-647 (1999)
- [Papadimitriou’94] Christos H. Papadimitriou: On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence. J. Comput. Syst. Sci. 48(3): 498-532 (1994)
- [Thomason’78] A. G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs, Ann. Discrete. Math. 3 (1978), 259-268.