Which of the following is an NP-Complete graph problem?

Options

  • A. Hamiltonian Cycle Problem
  • B. Depth First Search
  • C. Breadth First Search
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Hamiltonian Cycle Problem

Detailed Explanation

Hamiltonian Cycle is an NP-Complete problem. It asks whether a graph contains a cycle that visits every vertex exactly once and returns to the starting vertex. A proposed Hamiltonian cycle can be verified in polynomial time, which places the problem in NP. The problem is also NP-hard. Do not confuse Hamiltonian Cycle with ordinary graph traversal algorithms such as DFS and BFS, which can be performed in polynomial time, typically O(V + E) for adjacency-list representations.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts