|
|
Definition
Given a undirected graph G, there exists a hamiltonian cycle, if and only if there exists a cycle, in which every vertex is visited exactly once. Note that, one node can be allowed to close the cycle, so that node would visit twice.
Polynomial Certifier
Given a undirected graph G, Is there a simple cycle in which every vertex is visited exactly once?
Reduction from Directed Hamiltonian Cycle from simple case to general case
Given a directed graph G = (V, E), construct an undirected graph G’ with 3n nodes.
Claim 4.15.2.1. Directed Hamiltonian Cycle ≤ p Hamiltonian Cycle G contains Directed Hamiltonian Cycle if and only if G’ has Hamiltonian Cycle
G contains Directed Hamiltonian Cycle ⇒ G’ has Hamiltonian Cycle
Proof. Suppose G has a directed Hamiltonian cycle C. Then G’ has an undirected Hamiltonian cycle (same order). __
G’ contains Hamiltonian Cycle ⇒ G has Directed Hamiltonian Cycle
Proof. Suppose G’ has an undirected Hamiltonian cycle C’. C’ must visit nodes
in G’ using one of following two orders:
…,B,G,R,B,G,R,B,G,R,B,…
…,B,R,G,B,R,G,B,R,G,B,…
Blue nodes in C’ make up directed Hamiltonian cycle C in G, or reverse of
one. __
Reduction from Hamiltonian Path by Equivalence
Given a graph of Hamiltonian Path, we can build another graph G’, in which we
simply add an additional vertex u, and connect u to all other vertices. So
V ′ = V ∪{u}, and E′ = E ∪{(u,v)
v 
V }. We claim this new graph G’ contains a
Hamiltonian Cycle. Obviously, this construction can be done in polynomial time in
terms of |V | and |E|.
Claim 4.15.2.2. Hamiltonian Path ≡p Hamiltonian Cycle
G contains Hamiltonian Path if and only if G’ has Hamiltonian Cycle
G contains Hamiltonian Path ⇒ G’ has Hamiltonian Cycle
Proof. If G has a Hamiltonian Path, (v1,v2),(v2,v3),…,(vn-1,vn), then it is easy to observe that G’ has Hamiltonian Cycle (u,v1),(v1,v2),(v2,v3),…,(vn-1,vn),(vn,u) __
G’ has Hamiltonian Cycle ⇒ G contains Hamiltonian Path
Proof. Since the new vertex u has |V | many neighbors, (v1,…,vn). Thus, any Hamiltonian cycle in G’ must consecutively traverse any two of those edges, (u,vi),(vj,u). The rest of the cycle then traverses every other vertex on route from vi to vj. Thus deleting the two edges (u,vi),(vj,u) from the Hamiltonian Cycle gives a Hamiltonian path from vi to vj in the original graph G.
To simplify, if G’ has a Hamiltonian Cycle, (u,v1),(v1,v2),(v2,v3),…,(vn-1,vn),(vn,u), then it is easy to observe that G has (v1,v2),(v2,v3),…,(vn-1,vn) Hamiltonian Path __
