SAT ≤p MaxIS | Complexity Atlas

The construction

On a general CNF formula $\varphi$ with $m$ clauses — not necessarily 3CNF; clauses may be of any size. Build $G_\varphi=(V,E)$ :

Vertices. One vertex per literal occurrence in each clause. A literal appearing in several clauses gets several vertices, one per occurrence: a vertex represents an occurrence, not a variable.
Red edges (within a clause). For each clause, join every two vertices born from it — each clause becomes a clique.
Black edges (a literal and its negation). Join every vertex of a literal to every vertex of its negation.
Return $\langle G_\varphi,m\rangle$ .

What each colour does. The red edges ensure an independent set takes at most one vertex per clause — this is what caps the maximum at $m$ . The black edges ensure a literal and its negation are never both chosen — so the choice is consistent and translates into a legal assignment.

Visualization

φ = (x₁ ∨ ¬x₂) ∧ (¬x₁ ∨ x₂ ∨ x₃) ∧ (¬x₂ ∨ ¬x₃)m = 3 clauses

Vertex = one literal occurrence

Correctness — both directions

SAT ∈ ⟹ MaxIS ∈

Suppose $\varphi\in\mathrm{SAT}$ ; some assignment $\mathcal V$ satisfies it, i.e. for every clause there exists a literal valued $1$ . (Quantifier order matters: not "there exists a literal for every clause", which is far stronger and simply false.)

Let $U$ consist of one such vertex per clause. With $m$ clauses and vertices of distinct clauses being distinct, $|U|=m$ .

$U$ is independent. Let $x,y\in U$ be distinct.

A red edge? $U$ holds exactly one vertex per clause, so $x,y$ came from different clauses; red edges join only same-clause vertices.
A black edge? By choice, $\mathcal V$ values both corresponding literals $1$ . But a literal and its negation are never both $1$ , so $x,y$ are not a literal and its negation.

We are not done — that was only the "exists" half. The "for all" half is also needed:

Claim (maximality bound): every independent set in $G_\varphi$ has size $\le m$ . Let $\hat U$ be independent. Any two vertices of one clause are joined by a red edge, so $\hat U$ holds no two from one clause; there are $m$ clauses, so $|\hat U|\le m$ . Note the claim holds for every $\varphi$ , satisfiable or not — it depends only on the red edges.

Combining: an independent set of size $m$ exists, and every independent set has size $\le m$ . So $\alpha(G_\varphi)=m$ , i.e. $\langle G_\varphi,m\rangle\in\mathrm{MaxIS}$ .

MaxIS ∈ ⟹ SAT ∈

Suppose $\langle G_\varphi,m\rangle\in\mathrm{MaxIS}$ , i.e. $\alpha(G_\varphi)=m$ ; then some independent $U$ has $|U|=m$ .

$U$ is independent, so no two of its vertices carry a red edge; hence $U$ holds at most one vertex per clause.
Since $|U|=m$ and there are exactly $m$ clauses, with at most one per clause — by pigeonhole (in the tight direction) $U$ holds exactly one vertex per clause.

(These are two separate arguments: the first from independence, the second from counting.)

$U$ is independent, so no black edge joins its vertices; hence $U$ holds no two vertices for a literal and its negation.
The literals corresponding to $U$ 's vertices are therefore consistent: no variable occurs both positively and negatively. So there exists an assignment $\mathcal V$ satisfying all of them — give each variable occurring in the collection the value satisfying its occurrence, and the rest arbitrary values.
By item 2, $U$ holds a vertex from every clause, so $\mathcal V$ satisfies at least one literal in each clause, i.e. it satisfies $\varphi$ .

Hence $\varphi\in\mathrm{SAT}$ .

Cost of the reduction

TimeO(|φ|²)

SpaceO(|φ|²)

Output size|V| ≤ |φ|, |E| = O(|φ|²)

Creating the vertices is a single pass, $O(|\varphi|)$ , and in particular $|V|\le|\varphi|$ — each vertex is born of one literal occurrence. The edges require a pass over all pairs, $\binom{|V|}{2}=O(|V|^2)=O(|\varphi|^2)$ , each decision being a constant-time local test. Total $O(|\varphi|^2)$ .

Note that here, unlike $\mathrm{3SAT}\le_p\mathrm{IS}$ , clause length need not be bounded: the vertex count is the number of literal occurrences, linear in formula length whatever the clause sizes.

What it buys

$\mathrm{MaxIS}$ is NP-hard. With $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$ it is coNP-hard too, and the two together give the unusual result: $\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$ if and only if $\mathrm{NP}=\mathrm{coNP}$ .

Pitfalls

The forward direction needs two claims, not one. For $\mathrm{IS}$ it suffices to exhibit a set of size $m$ ; for $\mathrm{MaxIS}$ one must also rule out a larger one. That is exactly where the $\mathrm{SAT}\le_p\mathrm{IS}$ homework stops and the work here begins.
A "for all" claim opens with "let". The maximality bound is a statement about every independent set, so the proof must open "let $\hat U$ be independent" — only once the variable is introduced may one argue by contradiction.
"There exists an assignment", not "the assignment can be determined". There is no uniqueness: a variable not occurring in $U$ takes a free value, so several assignments fit. The proof also stops being algorithmic at this point — it proves existence implies existence, and an algorithmic argument is only one way to do that.

The chain

Rests on

A ∈ NP ≤p SAT

Used later by

co-IS ≤p MaxIS

Where this was read from

Lesson 22משפט 2: $\mathrm{SAT}\le_p\mathrm{MaxIS}$ , ולכן $\mathrm{MaxIS}$ היא NP-קשה
2025"Define $MAX\text{-}IS$ as the decision problem asking whether the maximum independent set has size exactly $k$ . Prove $MAX\text{-}IS$ is $NP$ -hard."