Question

9. Identify which of these problems are NP-complete and which can be exactly solved using a polynomial time algorithm

(a) Finding the vertex cover in a line graph

(b) Finding the maximum clique in a tree

(c) Finding the independent set in complete graph

(d) Finding the Hamiltonian cycle in a graph that has exactly one cycle

Answer 1

Answer;

Option (a).Finding the vertex cover in a line graph

Finding the vertex cover in a line graph NP-complete and which can be exactly solved using a polynomial time algorithm

Here,

Vertex cover in a line graph, maximum clique in a tree , independent set in complete graph and the Hamiltonian cycle in a graph that has exactly one cycle are NP-complete problems.

An algorithm is supposed to be solvable in polynomial time uncertainty the number of steps required to complete the algorithm for a given input is used for some non negative integer.

Polynomial-time algorithms are supposed to be fast and efficient. A polynomial is a combination of linear terms that look similar Constant * x^k.

If we needed a polynomial time algorithm we can solve all problems in NP in polynomial time.