Finding a Second Hamilton Circuit

De

Given an undirected graph does it have a Hamilton circuit ? It is well-known that this is an NP-complete problem. 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 :

Exercise : Prove that if a cubic graph has a hamilton circuit then it must have a second one

The above exercise is called Smith’s Theorem. Now consider the following computational poblem :

SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit.

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 [1] Papadimitriou defined several syntactic classes (e.g., PPA, PPAD, PPP) in TFNP. Papadimitriou proved that SMITH is in the complexity class PPA [1]. Here is an open problem mentioned in [1].

Open Problem : Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.

[1] 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)

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.

Open Problems

• Find a polynomial time algorithm for SMITH (or) Prove that SMITH is PPA-complete.
• Are there special cases of SMITH solvable in polynomial-time ?

References :

• [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.