Consider the following problem: Longest Path Given a graph G = (V, E) and an int
ID: 3776522 • Letter: C
Question
Consider the following problem: Longest Path Given a graph G = (V, E) and an integer k, determine whether there is a path in G of length k (edges) or larger. You are trying to prove that Longest Path is NP-complete. You come up with the following reduction from Hamiltonian Path to Longest Path. The reduction f takes and instance hG, x, yi of the Hamiltonian Cycle problem and produces the instance hG, |V | 1i of the Longest Path problem. Show that this is not a p m reduction from Hamiltonian Path to Longest Path.
Explanation / Answer
We rst show that the so-called Hamiltonian Path problem is NP-complete: Given an undirected graph G = (V;E), determine whether G contains a Hamiltonian path, i.e., a path that visits every vertex exactly once. It is easy
to verify that Hamiltonian Path is in NP.We show that HamiltonianCycle /Hamiltonian Path. Given an instance
G = (V;E) of Hamiltonian Cycle, weproceed as follows: For every edge e = fu; vg 2 E of G, construct an augmented graph Ge that consists of G and two additional vertices u0; v0 that are connected
to u and v, respectively, i.e., Ge = (V [fu0; v0g;E [fu0; ug[fv0; vg). Note that the following holds for every edge e 2 E: There is a Hamiltonian cycle in G using edge e if and only if there is a Hamiltonian path in Ge. Thus, there is
a Hamiltonian cycle in G if and only if there is a Hamiltonian path in Ge for
some edge e 2 E. Note that this reduction takes polynomial time.
Now it is easy to conclude that Longest Path is NP-complete because it is in
NP and HamiltonianP ath / LongestP ath simply by observing that there is a
Hamiltonian path in G if and only if there is a path of length n -1.