Is there a way to find the largest subgraph in a graph where every vertex in the subgraph is connected to every other vertex in the subgraph? Or is such a problem NP-Complete?

In math: $G = (V,E),$ $ S \subseteq G $ s.t. $\forall $ vertices $u,v$ in the vertex set of S there exists an edge $e$ for $\{u,v\}$ and S is the largest such set.

I thought that it wasn't because you could start at a node then search through its neighbors in a breadth first manner. Then check that previously visited nodes are all part of the node's neighbors and passing the number of vertices in the constructed graph so far. After execution ends you should have the largest subgraph made for that vertex and then you repeat for the other vertices.

Would this algorithm work in answering the question or am I missing something?


NP-Completeness deals with decision problems. So if you have the problem:
INSTANCE: Let $G$ be a graph and let $x \leq |G|$ be an integer.
DECISION: Does $G$ contain a subgraph isomorphic to $K_{x}$?

This is NP-Complete. The optimization variant (finding the largest $x$) is NP-Hard.

  • $\begingroup$ Sorry about that I changed some of the problem so it would be easier to formulate. In that case I'm asking find the subgraph that follows my preconditions where |V| > k, where k is some input $\endgroup$ – MichaelGofron Nov 29 '15 at 21:47
  • 2
    $\begingroup$ It's still the CLIQUE problem and still NP-Complete. $\endgroup$ – ml0105 Nov 29 '15 at 21:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.