The Independent Set (IS) problem is an NP-complete problem.


An independent set is defined as a subset of a vertices in a graph that are not connected together.


  • Does G have an independent set of at least size K?

Proof of Independent Set being NP-complete

(Reduce from 3-CNF-SAT a version of the Boolean satisfiability problem)

1. Certificate: Check that no vertices are connecting.

Can easily be verified in polynomial time.

2. 3-CNF-SAT->IS transformation

  • 3-CNF-SAT (Given):
    • Variables x1, x2, ..., xn
    • Clauses c1, c2, ..., cm
  • IS (Construction of Graph):
    • 1 vertex for each occurrence of each literal (3m vertices)
    • Connect two vertices when:
      • They are conflicting (i.e. x1, ~x1)
      • They are in the same clause

This transformation can be performed in polynomial time.

3. Proof of correctness (note: is not formal or complete)

  • Yes->Yes:
    • Pick only one literal from 3-CNF-SAT solution
    • Per definition of satisfiability, vertices in our graph represented by this literal will not be connected to another vertex in the ""same clause"" or to a conflicting vertex
    • Hence, the node is part of the Independent Set
  • No->No:
    • Use contrapositive (Yes<-Yes aka 3-CNF-SAT<-IS).
    • Select an independent set of size m.
    • By construction, vertices are linked to conflicting literals and literals in the same clause.
    • Therefore, these can not be part of an independent set.
    • Hence, only vertices in an independent set will satisfy 3-CNF-SAT.