Classify reach of die following statements as T true Ffalse

Classify reach of die following statements as T (true), F(false) or I (inconclusive). Justify (give reasoning far) your answers. The longest path problem, i.e. finding the longest simple path between any two vertices in a graph, is a P problem. Suppose that P1 is an NP-complete problem, and that P2 can be converted into PI by a polynomial bounded algorithm. Then P2 is also an NP-complete problem. Suppose that every vertex of a graph has degree 2. Then the graph is colorable with at most 3 colors. Suppose that C V is a vertex cover of die graph G. Then the independent set is I = V - C, i.e. if C is the set of vertices in die vertex cover, then the independent set is found by removing the C from die graphs vertices V.

Solution

1) False the longest path problem i.e., finding the longest simple path between any two vertices in a graph is not a problem.Let us consider a solution path S, and just check that this path have at least n edged and form a path with no repeated vertices. This reduction comes from Hamiltonian path. Let us take an instance of Hamiltonian Path on Graph, and create an instance of longest path G1, m like G1=g and m=|v-1|, here represents the vertices of Grapg G this means there exist a path whose length is which exist in Graph G1 iff G1 consist of Hamiltonian Path