Course contentsShow
← Computer Science
Lesson 1934 of 2,87243. Complexity TheoryFree lesson

3-SAT to Independent Set Reduction

Master the gadget-based reduction from 3-SAT to the Independent Set problem using graph construction.

3-SAT to Independent Set Reduction

You'll learn how to transform any 3-SAT problem into an Independent Set problem using a clever graph construction, proving that Independent Set is NP-complete.

The Core Idea

We already know 3-SAT is NP-complete. To prove Independent Set is also NP-complete, we need a polynomial-time reduction: given a 3-SAT formula, we build a graph where finding an independent set of size k corresponds exactly to satisfying the formula.

The Gadget Construction

For a 3-SAT formula with m clauses, we construct a graph as follows:

  1. Create a triangle for each clause: For clause (x ∨ y ∨ z), add three vertices (one per literal) and connect them in a triangle. These vertices represent the three possible ways to satisfy that clause.

  2. Connect contradictory literals: Add edges between vertices representing a variable and its negation across different triangles. For example, connect vertex x in clause 1's triangle to vertex ¬x in clause 2's triangle.

  3. Set k = m: We look for an independent set of size m (the number of clauses).

Why It Works

An independent set of size m must pick exactly one vertex from each triangle (since triangle vertices are all connected). This choice represents which literal satisfies each clause. The contradiction edges ensure we never pick both x and ¬x, guaranteeing a consistent variable assignment.

If the 3-SAT formula is satisfiable, we can pick m vertices (one per satisfied literal in each clause) with no edges between them. Conversely, any independent set of size m gives us a satisfying assignment.

Key Takeaway: The 3-SAT to Independent Set reduction uses triangle gadgets (one per clause) with contradiction edges between them, transforming logical satisfiability into a graph structure problem in polynomial time.