Which of the following is an NP-Complete problem?

Options

  • A. Binary Search
  • B. Shortest Path
  • C. Vertex Cover
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

C. Vertex Cover

Detailed Explanation

Vertex Cover is a well-known NP-Complete problem. Given a graph and an integer k, the decision version asks whether there exists a set of at most k vertices such that every edge has at least one endpoint in that set. Vertex Cover belongs to NP because a proposed set can be verified efficiently. It is also NP-hard through polynomial-time reductions from other NP-Complete problems. Binary Search and standard Shortest Path algorithms are polynomial-time problems.
← Previous Next →

Attempt Quiz Now:

BPSC TRE 4 DSA Practice set 1

Feature Posts