Directed Hamilton Cycle Problem is NP-complete

From ProofWiki
Jump to navigation Jump to search


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


Function Version is Reducible to Decision Version

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.

The directed graph $G$
A Hamilton cycle in $G$ if one exists


no solution if not.

Auxiliary Function
$f \left({G}\right) \to \left\{{0, 1}\right\}$ defined as:
$f \left({G}\right) = 1$ if and only if $G$ has a Hamilton cycle
$f \left({G}\right) = 0$ if and only if $G$ has no 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$.
add $u$ to the end of the solution set
remove the vertices $v_0$ and $u$ from $G$
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
$\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.

Every time $f \left({G}\right)$ is calculated at least one edge is removed.

Thus $f \left({G}\right)$ is called $O \left({n^2}\right)$ times.

This algorithm shows the functional problem polynomially reduces to the decision problem.

If the output of the functional problem is anything other than no solution then $G$ has a Hamilton cycle.

Thus the functional problem reduces to the the decision problem.

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.


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


verifying that each vertex in the sequence follows is adjacent to the previous vertex.

From NP Problem iff Solution Verifiable in Polynomial Time, a potential solution can be verified or rejected in polynomial time.

Thus the Hamilton Cycle Problem is NP.


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 $\left({A, B}\right)$ or $\left({B, A}\right)$ must be included in any Hamilton Cycle.

Likewise either $\left({C, D}\right)$ or $\left({D, C}\right)$ must be included.

The three cases for these four vertices are:

$\left({A, B, C, D}\right)$
$\left({A, B, E, C, D}\right)$
$\left({D, C, B, A}\right)$

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


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 $3 l + 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


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 $3 l m + 3 m + 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.



The Directed Hamilton Path Problem is NP-complete.

Proof of Corollary

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.