March 28, 2009 2:00 am

Finding a Second Hamilton Circuit

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)