HAMPATH is NP-complete

Hamiltonian path problem asks whether the input graph contains a path from  to  that goes through every node exactly once.

 is a directed graph with a Hamiltonian path from  to . 

HAMPATH is in NP

For the HAMPATH problem, a certificate for a string  HAMPATH simply is a Hamiltonian path from  to .

3SAT is polynomial time reducible to HAMPATH

We start the construction with a  -formula  containing  clauses,

where each  and  is a literal  or  Let  be the  variables of .

Now we show how to convert  to a graph  The graph  that we construct has various parts to represent the variables and clauses that appear in .

We represent each variable  with a diamond-shaped structure that contains a horizontal row of nodes.

We represent each clause of  as a single node.

The following figure depicts the global structure of  It shows all the elements of  and their relationships, except the edges that represent the relationship of the variables to the clauses that contain them.

Next, we show how to connect the diamonds representing the variables to the nodes representing the clauses. Each diamond structure contains a horizontal row of nodes connected by edges running in both directions. The horizontal row contains  nodes in addition to the two nodes on the ends belonging to the diamond. These nodes are grouped into adjacent pairs, one for each clause, with extra separator nodes next to the pairs.

If variable  appears in clause  we add the following two edges from the  th pair in the  th diamond to the th clause node.

If  appears in clause  we add two edges from the  th pair in the  th diamond to the  th clause node.

After we add all the edges corresponding to each occurrence of  or  in each clause, the construction of  is complete. To show that this construction works, we argue that if  is satisfiable, a Hamiltonian path exists from to  and, conversely, if such a path exists,  is satisfiable.

Suppose that  is satisfiable. To demonstrate a Hamiltonian path from  to  we first ignore the clause nodes. The path begins at  goes through each diamond in turn, and ends up at  To hit the horizontal nodes in a diamond, the path either zig-zags from left to right or zag-zigs from right to left; the satisfying assignment to determines which. If  is assigned TRUE, the path zig-zags through the corresponding diamond. If  is assigned FALSE, the path zag-zigs. 

So far, this path covers all the nodes in  except the clause nodes. We can easily include them by adding detours at the horizontal nodes. In each clause, we select one of the literals assigned TRUE by the satisfying assignment.

If we selected  in clause  we can detour at the  th pair in the  th diamond. Doing so is possible because must be TRUE, so the path zig-zags from left to right through the corresponding diamond. Hence the edges to the  node are in the correct order to allow a detour and return.

Similarly, if we selected  in clause  we can detour at the  th pair in the  th diamond because  must be FALSE, so the path zag-zigs from right to left through the corresponding diamond. Hence the edges to the node again are in the correct order to allow a detour and return. (Note that each true literal in a clause provides an option of a detour to hit the clause node. As a result, if several literals in a clause are true, only one detour is taken.) Thus, we have constructed the desired Hamiltonian path.

For the reverse direction, if  has a Hamiltonian path from  to  we demonstrate a satisfying assignment for  If the Hamiltonian path is normal - that is, it goes through the diamonds in order from the top one to the bottom one, except for the detours to the clause nodes-we can easily obtain the satisfying assignment. If the path zig-zags through the diamond, we assign the corresponding variable TRUE; and if it zag-zigs, we assign FALSE. Because each clause node appears on the path, by observing how the detour to it is taken, we may determine which of the literals in the corresponding clause is TRUE.

All that remains to be shown is that a Hamiltonian path must be normal. Normality may fail only if the path enters a clause from one diamond but returns to another. 

The path goes from node  to  but instead of returning to  in the same diamond, it returns to  in a different diamond. If that occurs, either  or  must be a separator node. If  were a separator node, the only edges entering  would be from  and  If  were a separator node,  and  would be in the same clause pair, and hence the only edges entering  would be from ,  and  In either case, the path could not contain node  The path cannot enter  from  or  because the path goes elsewhere from these nodes. The path cannot enter  from  because  is the only available node that  points at, so the path must exit  via . Hence a Hamiltonian path must be normal. This reduction obviously operates in polynomial time and the proof is complete.