Reduce 3SAT to Independent Set

Build the occurrence graph and prove both directions of correctness.

Problem

Given a 3CNF formula $\varphi=C_1\land\cdots\land C_m$, construct in polynomial time a graph $G$ such that $\varphi$ is satisfiable iff $G$ has an independent set of size $m$.

Hint 1

Create one vertex for each literal occurrence, not merely one per variable.

Hint 2

Prevent two kinds of incompatible choices: two occurrences from one clause, and complementary literals from different clauses.

Full solution

For each literal occurrence in each clause, create a vertex. Join every pair of vertices belonging to the same clause. Also join vertices labeled $x$ and $\neg x$, wherever those occurrences appear. Set $k=m$.

If $\varphi$ has a satisfying assignment, choose one true literal occurrence from each clause. No two chosen vertices are in one clause, and no chosen literals are complementary under one assignment, so they form an independent set of size $m$.

Conversely, an independent set of size $m$ contains at most one vertex from each clause clique, hence exactly one from every clause. It contains no complementary pair. Assign every selected positive literal true and every selected negative literal false; consistency follows from the missing conflict edges. Extend unassigned variables arbitrarily. Each clause has its selected true literal, so $\varphi$ is satisfied.

There are $3m$ vertices and at most $O(m^2)$ edges, so construction time and output size are polynomial.

Checkpoint

The converse must explain both “one per clause” and why selected literals extend to one consistent assignment.

Provenance note

This is an independently written presentation of a standard reduction. Student work is not treated as an authoritative source.

Common mistakes

• Skipping a direction of correctness or an input-format edge case.
• Measuring resources against a numeric value rather than encoded input length.
• Treating an informal intuition as a proof of the stated bound.

Sources and verification

• Merged summary, pp. 55-57
• 2026 transcript 14 (graph-reduction context)
• Sipser 3e, sec. 7.5
• Garey-Johnson, GT20
• Catalog mapping: data/exercises.json; statements and solutions are independently written; personal submissions are non-authoritative.

Open in the visualization gallery: 3SAT → Independent Set