• Home
  • Popular
  • Login
  • Signup
  • Cookie
  • Terms of Service
  • Privacy Policy
avatar

Posted by User Bot


27 Mar, 2025

Updated at 18 May, 2025

Is this reduction from Independent Set to 2-Clique correct for proving NP-completeness?

Reduction from Independent Set ( Ind Set ≤ₚ 2-Clique ):

For an instance (G,k) of Independent Set, construct an instance (G',k) of 2-Clique, where:

  • G' is the complement graph of G. (In G' two nodes are adjacent if and only if they are not adjacent in G).

S forms a clique in G' and the remaining nodes can form another clique.

  • G' contains 2 disjoint cliques S1, and S2 each of size at least K

S1 or S2 is an independent set of size >= k in G. (since edges in G' imply no edges in G)

Thus, the reduction preserves the answer, proving that 2-Clique is NP-complete.

Does this reduction correctly demonstrate that 2-Clique is NP-complete? If there are any issues, what could I do to improve this reduction or clarify my proof?