NP-completeness of longest path Longest Path(Decision Version) Given a graph G and an integer k, decide whether G contains a simple path of length greater than k Part 1 (Longest Path in NP) Given any sequence of vertices, it's easy to check the length and whether the sequence is a path so longest path is in Np Part 2(reduce special case to general form) The Longest Path contains Hamiltonian Path(k= n)as a special case, so we can reduce hamiltonian Path( known in NPC)to Longest Path directlyNP-completeness of Longest Path Longest Path (Decision Version) Given a graph G and an integer k, decide whether G contains a simple path of length greater than k • Part 1 (Longest Path in NP) Given any sequence of vertices, it’s easy to check the length and whether the sequence is a path, so Longest Path is in NP • Part 2 (reduce special case to general form) The Longest Path contains Hamiltonian Path (k = n) as a special case, so we can reduce Hamiltonian Path (known in NPC) to Longest Path directly 16