|
|
Definition
Given a undirected graph G, there exists a hamiltonian path, if and only if there exists a path, in which every vertex is visited exactly once.
Polynomial Certifier
Given a undirected graph G, Is there a simple path in which every vertex is visited exactly once?
Reduction from Hamiltonian Cycle by Equivalence
Given a Graph G of Hamiltonian Cycle, we construct another graph G’ as following: Pick a arbitrary vertex v in G, create three new vertices x, y and z and add edges (x, v), (y, z) and an edge from each neighbor of v to z. We call this new Graph G’, and G’ contains Hamiltonian Path. Obviously, this construction can be done in polynomial time in terms of |V | and |E|
Claim 4.15.1.1. Hamiltonian Cycle ≡p Hamiltonian Path
G contains Hamiltonian Cycle if and only if G’ has Hamiltonian Path
G contains Hamiltonian Cycle ⇒ G’ has Hamiltonian Path
Proof. If G has a simple cycle C containing all vertices, then it contains an edge (v,w) incident on v. We break the cycle C into a simple path P in G’ containing all vertices by removing edge (v,w) from C to obtain a path P′ = v,v1,…,w from v to w and then setting P = xP’zy. __
G’ contains Hamiltonian Path ⇒ G has Hamiltonian Cycle
Proof. If G’ has a simple path P containing all vertices, then it begins at x and ends at y. We transform P into a simple cycle in G containing all vertices by removing x, y and z. Since the first vertex of P is v and the last of P is a neighbor of v, the resulting sequence of vertices is a simple cycle in G containing all vertices. __
