Given a graph , a Hamiltonian path from nodes to is a directed path from to that traverses every node exactly once. We define the language.
NP-Complete
Info
is NP-complete
Given a path, we can verify if it is Hamiltonian by checking if it traverses every node exactly once. Thus . To show completeness, we reduce from 3SAT.
Let be a 3cnf formula with clauses. Each character represents some literal or . For each variable , create a line of nodes, with a path going left and right. For every 3 nodes from left to right, assign the last 2 nodes from the th group to the th clause.
Now for each clause , create a corresponding node. If contains , add a edges to form a clockwise loop with the previously assigned nodes. If it contains , make a counterclockwise loop instead. (below is an example of a clockwise loop)
Now we add intermediate nodes to connect each of the variable gadgets as follows, and link the top and bottom of these gadgets to start node and end node .
Any path from to must traverse every horizontal strip of nodes. This is because we cannot use the clause gadgets to take a detour, as the adjacent separator nodes in each horizontal strip could not be traversed.
If we walk from left to right for , we assign true to that variable. Otherwise, we assign false. When a path travels through a clause gadget, that indicates the current strip’s assignment satisfies that clause. Thus there is a correspondence between Hamiltonian paths of and satisfying assignments to . This reduction is done in polynomial time, so is NP-complete.
Undirected Hamiltonian Path
If we replace undirected graph with a directed graph, we have a new language .
NP-Complete
Info
is NP-complete
By similar reasoning to , .
Let be a directed graph with nodes and . We will construct an undirected graph , where a path corresponds exactly to some path for . For every node add , , and to , while adding edges . Set and . For every edge in , add an edge . Any resulting path from must follow the pattern
The edges inside each gadget are forced, thus the remaining edges will give a path from in . The Hamiltonian property is transitive through this, thus we have a polytime reduction to and is NP-complete.
