Consider the following two problems of graph. 1) Given a graph, find if the…
2015
Consider the following two problems of graph. 1) Given a graph, find if the graph has a cycle that visits every vertex exactly once except the first visited vertex which must be visited again to complete the cycle. 2) Given a graph, find if the graph has a cycle that visits every edge exactly once. Which of the following is true about above two problems.
- A.
Problem 1 belongs NP Complete set and 2 belongs to P
- B.
Problem 1 belongs to P set and 2 belongs to NP Complete set
- C.
Both problems belong to P set
- D.
Both problems belong to NP complete set
Attempted by 55 students.
Show answer & explanation
Correct answer: A
Problem 1 (Hamiltonian cycle): The decision asks whether there exists a cycle that visits every vertex exactly once and returns to the start. This is the Hamiltonian cycle problem.
Classification: NP-complete. A proposed Hamiltonian cycle can be verified in polynomial time, and the problem is known to be NP-hard by standard reductions, so it is NP-complete.
Problem 2 (Eulerian cycle): The decision asks whether there exists a cycle that uses every edge exactly once. This is the Eulerian cycle problem.
Classification: In P. There is a simple polynomial-time test to decide whether an Eulerian cycle exists.
For an undirected graph: check that every vertex has even degree and that all vertices with nonzero degree belong to a single connected component. If both hold, an Eulerian cycle exists. These checks take O(V + E) time.
For directed graphs: check that every vertex has equal in-degree and out-degree and that all vertices with nonzero degree belong to a single strongly connected component when considered appropriately; these checks are also polynomial-time.
Conclusion: The first problem (Hamiltonian cycle) is NP-complete, while the second problem (Eulerian cycle) is solvable in polynomial time (in P).
A video solution is available for this question — log in and enroll to watch it.