|
|
Definition
Given a digraph G = (V, E), find the longest path in the graph.
Polynomial Certifier
Given a digraph G = (V, E), does there exists a simple path of length at least k edges?
Reduction from 3SAT by encoding with gadget
Reduction from Hamiltonian Path from simple case to general case
Given a graph G with n vertices, let k = n- 1. Then < G,k > is an instance of Longest Path.
Claim 4.15.5.1. Hamiltonian Path ≤ p Longest Path (This construction of
Hamiltonian Path leads to is a special case of Longest Path)
We have a graph G that contains a Hamiltonian Path, if and only if G has a
longest path of length |V |- 1.
G contains a Hamiltonian Path ⇒ G has a Longest Path of length |V |- 1.
Proof. Assume G is not a Hamiltonian path of size |V |, then it means G visits all vertices, which means there exists a path of which length is |V |- 1. This is exactly the definition of LP. __
G has a Longest Path of length |V |- 1 ⇒ G contains a Hamiltonian Path.
Proof. Conversely, if G forms a Longest Path of size |V |- 1, then we know that a simple path of length n- 1 must contain n vertices and hence must be a Hamiltonian Path. __
