Question

Note: For the following problems, you can assume that INDEPENDENT SET, VERTEX COVER, 3-SAT, HAMILTONIAN PATH, and GRAPH COLORING are NP-complete. You, of course, may look up the defini- tions of the above problems online. 5. The LONGEST PATH problem asks, given an undirected graph G (V, E), and a positive integer k , does G contain a simple path (a path visiting no vertex more than once) with k or more edges? Prove that LONGEST PATH is NP-complete.

Answer 1

Given that:

Solu tian cam lone in polynomial Hm The longesfpolhfs Np hand byeust fo loos aum cO

houd 0% mochine machineecides them accepf olsfeet c、 99 all -tests fs easy to see tht all-he tets can be

horoL we heel shot, that Is byt UHAoP Fath art maps every ip ab ion clenaly takes an amoumt ) e l Cleas

nition ath is h-l. hodes nhe Cr う Contain o Srnple p th 먼 length at least mple e o- mef once,

a. Ham he preot 1s Comp 1sComplea ALe.