Directed Hamilton Cycle Problem is NP-complete

From ProofWiki
Jump to: navigation, search

Problem

There are two versions of the Directed Hamilton Cycle Problem.

The function version:

Given a directed graph $G$ with $n$ vertices find a Hamilton Cycle in $G$.

The decision version:

Given a directed graph $G$ with $n$ vertices determine if $G$ has a Hamilton Cycle.

Theorem

Both versions of the Directed Hamilton Cycle problem are NP-complete.

Proof

The Function Version of the Problem is Reducible to the Decision Version of the Problem

The algorithm described below solves the function version of the problem with $O \left( {n^2} \right)$ calls of the decision version of the problem.

Input: The directed graph $G$

Output: A Hamilton Cycle in $G$ if one exists or "no solution" if it doesn't.

Auxiliary Function: $ f\left( G \right) \to \{0,1\}$ where $f\left( G \right) = 1$ iff $G$ has a Hamilton Cycle.

If $f \left( G \right) = 0$ output "no solution". Pick a starting vertex. Call it $v_0$. The solution path starts at $v_0$. While $G$ has more then one vertex:

Pick one of the edges going out of $v_0$. Call that edge $\left({v_0,u}\right)$.
If $f \left( {G - \left( {v_0 , u} \right) } \right) = 1$ remove $\left({v_0,u}\right)$ from $G$
Otherwise add $u$ to the end of the solution set and remove the vertices $v_0$ and $u$ from $G$ and replace them with a new $v_0$ where $\left( {v_0 , w} \right)$ is in the new graph if $\left( {u , w} \right)$ is in the old graph, and $\left( {w , v_0} \right)$ is in the new graph if $\left( {w , v_0} \right)$ is in the old graph.

Finally add $v_0$ to the end of the solution path and we have our solution.

Because every time $f \left( G \right)$ is calculated at least one edge is removed $f \left( G \right)$ is called $O\left( {n^2} \right)$ times. This algorithm shows the functional problem polynomially reduces to the decision problem. The functional problem also reduces to the the decision problem because if the output of the functional problem is anything other then "no solution" then $G$ has a Hamilton Cycle. Because they are mutually polynomially reducible we can show that both are NP or NP-hard by showing that either of them are NP or NP-hard. $\Box$

The Directed Hamilton Cycle Problem is NP

Given a potential solution to the decision problem in the form of a sequence of vertices it is possible to determine if that sequence is a Hamilton Cycle by making sure every vertex appears exactly once and verifying that each vertex in the sequence follows is adjacent to the previous vertex.Because a potential solution can be verified or rejected in polynomial time the Hamilton Cycle Problem is NP. $\Box$


The Directed Hamilton Cycle Problem is NP-hard

The objective here is to polynomially reduce the Conjunctive Normal Form Satisfiability problem with $m$ variables and $l$ clauses to the decision version of the Directed Hamilton Cycle problem. Because CNF Satisfiability Problem is NP-Complete that is enough to show the Hamilton Cycle is NP-hard.

Consider the following diagram of a part of a graph:

CNF to HAMILTONIAN graph.jpg

It is clear that either $(A,B)$ or $(B,A)$ must be included in any Hamilton Cycle. Likewise either $(C,D)$ or $(D,C)$ must be included. The three cases for these four vertices are:

$(A,B,C,D)$
$(A,B,E,C,D)$
$(D,C,B,A)$

In short, the four vertices $A,B,C,D$ must be visited in order or in reverse order. Also, they can only visit the $E$ node if they are in the right order. These pieces of the graph can be concatenated by letting the $D$ node of one piece be the same as the $A$ node of the next.

The final graph to be constructed takes a form similar to the following diagram: CNF to HAMILTONIAN graph2.jpg

The boxes represent concatenations of the pieces we have just studied. In the final graph there will be one of these rows for every variable in the CNF SAT problem, each one linked to another row as shown here. (This creates a circuit through the rows.) A left to right path corresponds to the variable being true and a right to left path corresponds to the variable being false.

In addition to these vertices there will also be one vertex for every clause in the original problem. These will take the $E$ vertex position in the first diagram. A vertex will have be attached to a pair of vertices in a row if the variable the row corresponds to appears in the clause, going left to right if the variable is not negated and right to left if it is negated. In the image the $E$ type node would contain $x_1 \lor \neg x_2$ if the first row corresponded to $x_1$, and the second to $x_2$.

Clearly all the vertices could only be visited in a cycle if there was some choice of direction for each of the rows that allowed all the $E$ type vertices to be visited. That would only happen if there was some way of deciding values for the variables in the CNF SAT problem that gave each clause at least one true variable in its conjunction. And so the graph has a Hamilton Cycle iff the CNF SAT problem has a solution.

The number of vertices in a given row is at most $3l + 3$ because each variable can only appear in each clause once (Otherwise that clause is either internally redundant or trivially satisfied), each additional instance of a variable only requires three additional vertices, and there are only three nodes of overhead. The number of $E$ type vertices is $l$. Therefore the total number of vertices in the constructed graph is at most $3lm + 3m + l$ vertices. Because the size of the graph is bounded by a polynomial of the size of the CNF SAT problem this scheme is a polynomial reduction from CNF SAT to the directed Hamilton Cycle problem.

The Directed Hamilton Cycle problem is NP-hard.

Because the Directed Hamilton Cycle problem is NP and NP-hard it is NP-complete $\blacksquare$.

Corollary: The Directed Hamilton Path Problem is NP-complete

The proof is exactly the same as before, except instead of having all the rows in a complete circuit there is a gap, giving the Hamilton Path a definite starting and stopping point.