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.*

### Like this:

Like Loading...