5. Hamiltonian Cycle Problem

Hamiltonian Cycle Problem (HAMILTONIAN)

The Hamiltonian Cycle Problem (HAMILTONIAN) takes an input of:

• an undirected graph $G=(V,E)$

It provides an output of $\top$ if and only if $G$ contains a Hamiltonian cycle.

Link to original

Theorem: Hamiltonian Cycle Problem belongs to NP

Input: Given an undirected graph $G=(V,E)$

1. Decide whether $G$ contains a Hamiltonian cycle by checking every permutation of the vertices. However there are $n!$ possible permutations which is not polynomial.
2. However, an NDTM can check each permutation in parallel. Since each permutation requires us to only check $n$ edges, this is in polynomial time.

Theorem: The SAT problem is polynomially reducible to the Hamiltonian cycle problem, $\text{SAT}{\le }_p\text{HAMILTONIAN}$.

Input: Formula $F$ in CNF.

1. We want to construct a graph $G_F$ such that $F$ is satisfiable if and only if $G_F$ has a Hamiltonian cycle.
2. We make use of the following “gadget”:

This gadget has only two possible Hamiltonian paths through:

e.g. let’s construct a graph for $F=(P\vee \neg Q)\wedge (\neg P\vee \neg R)$.

• We start by placing one gadget for each variable.
• We connect the bottom of each gadget to the top of the next gadget (looping back around at the last one).
• We create a vertex for each clause.
• Let’s assume that going down the left path of the gadget means the variable is true, otherwise it is false.
• We connect the first vertex going left to right to indicate that the variable ($P$) must be true to satisfy the vertex.
• We continue to wire up the rest of the variables from each vertex corresponding to the desired value.
• We can make $F$ sastifiable when:

$P,Q$ are true $R$ is false	$P,Q,R$ are false

• Hence, we have that $F$ is satisfiable $⟺$ $G_F$ contains a Hamiltonian cycle. Therefore $\text{SAT}{\le }_p\text{HAMILTONIAN}$.

Theorem: HAMILTONIAN is NP-complete

Since SAT is NP-hard, it follows that the Hamiltonian Cycle Problem must also be NP-hard. This gives us our lower-bound which proves HAMILTONIAN is NP-complete.