co-IS ≤p MaxIS | Complexity Atlas

The construction

The complement lemma (from lesson 21). Let $f$ be polynomial-time computable. Then $f$ is a reduction from $A$ to $B$ iff it is a reduction from $\overline A$ to $\overline B$ — since $x\in A\iff f(x)\in B$ is logically equivalent to $x\notin A\iff f(x)\notin B$ . That is what licenses starting from $\overline{\mathrm{IS}}$ .

The reduction. On input $\langle G,k\rangle$ with $G=(V,E)$ :

Add $k-1$ new vertices to $G$ ; write $\hat V=V\cup(\text{the new ones})$ , so $|\hat V\setminus V|=k-1$ .
Add edges from every new vertex to every vertex of $V$ . Among the new vertices there are no edges, and among the vertices of $V$ nothing was added or removed.
Return $\langle\hat G,k-1\rangle$ .

The intuition. We want " $G$ has no independent set of size $k$ " to become a question about a maximum. If there is none, the maximum in $G$ is at most $k-1$ — but nothing guarantees it is exactly $k-1$ . So we plant an independent set of size exactly $k-1$ . Isolated vertices would not do: they would join the old sets and raise the maximum. Joining each new vertex to every old one lets the new set exist without mixing.

Visualization

⟨G, k⟩ = ⟨C₅, 4⟩co-IS: does G have no independent set of size 4?

Complement lemmaf reduces A to B ⇔ f reduces Ā to B̄ — so a reduction may start from co-IS.

Original vertex of VSolid: original edge of GIndependent set under discussion, ✓ ringed

Correctness — both directions

co-IS ∈ ⟹ MaxIS ∈

Suppose $\langle G,k\rangle\in\overline{\mathrm{IS}}$ — that is, $G$ has no independent set of size $k$ . Both halves of the $\mathrm{MaxIS}$ conjunction must be proved:

(a) Existence. The set $\hat V\setminus V$ (the new vertices) is independent in $\hat G$ : no edge was added between two new vertices. Its size is exactly $k-1$ . ✓

(b) The "for all" half. Let $U\subseteq\hat V$ be independent in $\hat G$ . In $\hat G$ there is an edge between every new vertex and every old one, so $U$ cannot hold both a new and an old vertex; hence $U\subseteq\hat V\setminus V$ or $U\subseteq V$ .

If $U\subseteq\hat V\setminus V$ : then $|U|\le k-1$ .
Otherwise $U\subseteq V$ : since no edge among $V$ 's vertices was added or removed, a set independent in $\hat G$ and contained in $V$ is independent in $G$ too. As $G$ has no independent set of size $k$ , and by heredity none of size greater than $k$ either (else drop vertices to get one of size exactly $k$ ), we get $|U|\le k-1$ .

Either way $|U|\le k-1$ . ✓

From both halves: the maximum in $\hat G$ is exactly $k-1$ , i.e. $\langle\hat G,k-1\rangle\in\mathrm{MaxIS}$ .

MaxIS ∈ ⟹ co-IS ∈

Suppose $\langle\hat G,k-1\rangle\in\mathrm{MaxIS}$ . We must show $\langle G,k\rangle\in\overline{\mathrm{IS}}$ , i.e. every independent set $U$ in $G$ has $|U|\ne k$ . This is a "for all" claim, so it opens with "let".

Let $U\subseteq V$ be independent in $G$ .

The reduction added no edge among the vertices of $V$ — the only edges added leave the new vertices. So $U$ , as a subset of $\hat V$ , is independent in $\hat G$ too.
By assumption $\alpha(\hat G)=k-1$ , so every independent set in $\hat G$ has size $\le k-1$ . In particular $|U|\le k-1$ .
Hence in particular $|U|\ne k$ .

As this holds for every independent $U$ in $G$ , there is no independent set of size $k$ , i.e. $\langle G,k\rangle\in\overline{\mathrm{IS}}$ .

Cost of the reduction

TimeO(|⟨G,k⟩|²)

SpaceO(|V|²)

Output size|V| + k − 1 vertices, |E| + (k−1)|V| edges

A subtle point: in the input encoding the number $k$ occupies only $\log k$ bits, so nothing may be bounded "in terms of $k$ ". But w.l.o.g. $k\le|V|$ — if $k>|V|$ then $G$ certainly has no independent set of size $k$ (it has no $k$ vertices at all), and the reduction returns a fixed string belonging to $\mathrm{MaxIS}$ . So $k-1<|V|$ , adding the vertices costs $O(|V|)$ , and adding the edges costs $(k-1)\cdot|V|=O(|V|^2)$ .

Note: each new vertex gets an edge to each old vertex, i.e. $|V|$ edges — not $k$ edges.

What it buys

$\mathrm{MaxIS}$ is coNP-hard. With $\mathrm{SAT}\le_p\mathrm{MaxIS}$ it is NP-hard as well, and the two together produce the situation where $\mathrm{MaxIS}\in\mathrm{NP}\cup\mathrm{coNP}$ if and only if $\mathrm{NP}=\mathrm{coNP}$ .

Pitfalls

Isolated vertices do not work. "Add $k-1$ isolated vertices" is nearly right — but isolated vertices join any existing independent set and raise the maximum by $k-1$ , so the "for all" half breaks.
"No set of size $k$ " implies "none of size $>k$ " — by heredity: drop a vertex from an independent set of size $k+1$ to get one of size $k$ . That is an argument of the proof, not of the algorithm: the algorithm never touches independent sets, only the graph.
$k=0$ needs separate handling. For every graph $\langle G,0\rangle\in\mathrm{IS}$ (the empty set), so $\langle G,0\rangle\notin\overline{\mathrm{IS}}$ ; on such input the reduction returns a fixed string outside $\mathrm{MaxIS}$ .

The chain

Rests on

SAT ≤p MaxIS

Where this was read from

Lesson 22משפט 3: $\overline{\mathrm{IS}}\le_p\mathrm{MaxIS}$ , ולכן $\mathrm{MaxIS}$ היא coNP-קשה

The $k=0$ case appears in none of the lesson's sources — it is a completion written into the lesson file itself so the construction is defined on every input.