SAT to Independent Set (Karp Reduction)

Definition

SAT to Independent Set

There is a polynomial-time many-one reduction from the SAT problem to the Independent Set problem:

$$\mathrm{SAT}{\le }_m^p\mathrm{INDEPENDENT}\mathrm{SET}.$$

Construction

Take a SAT instance in conjunctive normal form

$$F=C_1\wedge \cdots \wedge C_m,C_i={\ell }_{i,1}\vee \cdots \vee {\ell }_{i,r_i}.$$

Construct an independent set instance $(G,k)$ as follows:

1. Create one vertex $v_{i,j}$ for every occurrence of a literal ${\ell }_{i,j}$. Occurrences of the same literal in different clauses are distinct vertices.
2. For each clause $C_i$, join all of its vertices pairwise, making them a clique. An independent set can therefore contain at most one vertex from each clause.
3. Join two vertices from different clauses whenever their literals are complementary: one represents $x$ and the other represents $\neg x$. An independent set therefore cannot choose incompatible truth values for one variable.
4. Set $$k=m.$$

The graph is covered by $m$ clause cliques. Hence every independent set has size at most $m$, and an independent set of size at least $k=m$ must choose exactly one literal-vertex from every clause.

Correctness

The formula $F$ is satisfiable if and only if the constructed graph $G$ has an independent set of size at least $k=m$.

Correctness

Forward

Suppose that an assignment satisfies $F$. Every clause then contains a true literal. Choose one such literal-vertex from each clause clique. No two chosen vertices lie in the same clique. Moreover, two complementary literals cannot both be true under one assignment, so no two chosen vertices are joined by a conflict edge. The $m$ chosen vertices therefore form an independent set of size $m=k$.

Backward

Suppose that $G$ has an independent set $S$ with $|S|\ge m$. Since $S$ contains at most one vertex from each of the $m$ clause cliques, it follows that $|S|=m$ and $S$ contains exactly one vertex from every clause. No selected literals are complementary because every complementary pair is joined by a conflict edge. Assign each variable according to its selected occurrences and assign all remaining variables arbitrarily. This assignment makes every selected literal true, so every clause contains a true literal and $F$ is satisfiable.

Running time

Let

$$L=\sum _{i=1}^m{r}_i$$

be the number of literal occurrences in $F$. The construction creates $L$ vertices and at most $O(L^2)$ edges, so both its running time and its output size are polynomial in the input size. For a SAT input not already in CNF, a polynomial-size equisatisfiable CNF can first be obtained by introducing names for subformulas.

NP-completeness

SAT is NP-hard, so the reduction proves that Independent Set is NP-hard. Together with membership in NP, this proves that Independent Set is NP-complete.

Example

Four clauses

Consider

$$F=(a\vee b\vee c)\wedge (a\vee \neg b\vee \neg d)\wedge (\neg a\vee c\vee d)\wedge (b\vee \neg c\vee \neg d).$$

The reduction creates four three-vertex clause cliques and sets $k=4$. It also adds conflict edges between every pair of occurrences labelled $a$ and $\neg a$, $b$ and $\neg b$, $c$ and $\neg c$, or $d$ and $\neg d$.

Using subscripts to identify clauses,

$$S=\{a_1,a_2,c_3,b_4\}$$

is an independent set of size $4$: it chooses one vertex from each clause and contains no complementary pair. The corresponding assignment $a=b=c=\top$ satisfies all four clauses; $d$ may be assigned arbitrarily.