The following slideshow shows that an instance of the 3-CNF
Satisfiability (3-SAT) problem can be reduced to an instance of
Hamiltonian Cycle in polynomial time.
A trivial change in the construction will allow reduction from 3-SAT
to the Hamiltonian Path problem.
This slideshow explains the reduction (in polynomial time) of an instance of 3CNF Satisfiability (3-SAT) to an instance of the Hamiltonian Cycle problem.
$$x_1$$
. . .
$$x_2$$
. . .
$$x_3$$
. . .
$$s$$
$$t$$
$$C_1$$
$$C_2$$
s
t
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
1
2
3
4
5
6
7
8
9
C1
C2
$$x_1$$
$$x_2$$
$$x_3$$
1. Any Hamiltonian Cycle in the constructed graph ($G$) traverses $P_i$ either from right-to-left or left-to-right. This is because any path entering a node $v_{i,j}$ has to exit from $v_{i,j+1}$ either immediately or via one clause-node in between, in order to maintain Hamiltonian property Similarly all paths entering at $v_{i,j-1}$ has to exit from $v_{i,j}$.
2. Since each path $P_i$ can be traversed in $2$ possible ways and we have $n$ paths mapping to $n$ variables, there can be $2^n$ Hamiltonian cycles in the graph $G$ - {$C_1$, $C_2$ $\cdots$ $C_k$}. Each one of this $2^n$ Hamiltonian cycles corresponds to a particular assignment for variables $x_1$, $x_2$ $\cdots$ $x_n$.
3. This graph can be constructed in polynomial time.
1. If there exists a Hamiltonian cycle $H$ in the graph $G$, If $H$ traverses $P_i$ from left to right, assign $x_i = True$ If $H$ traverses $P_i$ from right to left, assign $x_i = False$
Since H visits each clause node $C_j$, at least one of $P_i$ was traversed in the right direction relative to the node $C_j$ The assignment obtained here satisfies the given 3 CNF.
2. If there exists a satisfying assignment for the 3 CNF, Select the path that traverses $P_i$ from left-to-right if $x_i = True$ or right-to-left if $x_i = False$ Include the clauses in the path wherever possible. Connect the source to $P_1$, $P_n$ to target and $P_i$ to $P_{i+1}$ appropriately so as to maintain the continuity of the path Connect the target to source to complete the cycle
Since the assignment is such that every clause is satisfied, all the clause-nodes are included in the path. The $P_i$ nodes and source and target are all included and since the path traverses unidirectional, no node is repeated twice The path obtained is a Hamiltonian Cycle
