|
|
Definition
Given a directed graph G, there exists a hamiltonian cycle, if and only if there exists a cycle, in which every vertex is visited exactly once.
Polynomial Certifier
Given a directed graph G, Is there a simple cycle in which every vertex is visited exactly once?
Reduction from 3-SAT by encoding with gadget
Given 3-SAT instance Φ with n variables xi and k clauses. Construct G to have 2n Hamiltonian cycles. Intuition: traverse path i from left to right if and only if set variable xi = 1 Obviously this construction can be done in polynomial time.
Claim 4.15.3.1. 3-SAT ≤p Directed Hamiltonian Cycle
Φ is satisfiable if and only if G has a Directed Hamiltonian Cycle
Φ is satisfiable ⇒ G has a Directed Hamiltonian Cycle
Proof. Suppose 3-SAT instance has satisfying assignment x*. Then, define Hamiltonian cycle in G as follows: if x *i = 1, traverse row i from left to right if x*i = 0, traverse row i from right to left for each clause Cj , there will be at least one row i in which we are going in ”correct” direction to splice node Cj into tour __
G has a Directed Hamiltonian Cycle ⇒ Φ is satisfiable
Proof. Suppose G has a Hamiltonian cycle C. If C enters clause node Cj , it must depart on mate edge. thus, nodes immediately before and after Cj are connected by an edge e in G removing Cj from cycle, and replacing it with edge e yields Hamiltonian cycle on G\{Cj} Continuing in this way, we are left with Hamiltonian cycle C’ in G\{C1,C2,…,Ck}. Set x*i = 1 if and only if C’ traverses row i left to right. Since C visits each clause node Cj , at least one of the paths is traversed in ”correct” direction, and each clause is satisfied. __
