Which of the following is an NP-Complete problem related to finding a fully connected subset of vertices in a graph?

Options

  • A. Clique Problem
  • B. Breadth First Search
  • C. Dijkstra Algorithm
  • D. More than one of the above
  • E. None of the above

Correct Answer (Detailed Explanation is Below)

A. Clique Problem

Detailed Explanation

Clique is an NP-Complete graph problem. A clique is a subset of vertices in an undirected graph in which every pair of vertices is connected by an edge. The decision version asks whether a graph contains a clique of size at least k. A proposed clique can be verified in polynomial time, so the problem is in NP. The Clique problem is also NP-hard. Related graph problems such as Independent Set and Vertex Cover are connected through polynomial-time reductions and are important topics in computational complexity.