NP-Hardness Part 3 (Clique, Vertex Cover)

Lecture slides (PDF)

Clique

Definition (Clique). A clique in a graph $G = (V, E)$ is a set $S \subseteq V$ such that every pair of vertices in $S$ is connected by an edge. Equivalently, the subgraph induced by $S$ is a complete graph $K_{\lvert S \rvert}$. The Clique decision problem asks: given $G$ and an integer $k$, does $G$ contain a clique of size $\ge k$?

Clique is in NP: given a set $S$ as a certificate, verify $\lvert S \rvert \ge k$ and check all $\binom{\lvert S \rvert}{2}$ pairs for edges in $O(k^2)$ time.

Reduction: Independent Set $\le_p$ Clique

Complement graph. The complement $\bar{G}$ of $G = (V, E)$ has vertex set $V$ and edge set $\bar{E} = \binom{V}{2} \setminus E$: an edge is present in $\bar{G}$ iff it is absent in $G$. Computing $\bar{G}$ from $G$ takes $O(V^2)$ time.

Key observation. $S \subseteq V$ is an independent set in $G$ $\iff$ $S$ is a clique in $\bar{G}$.

Proof. $S$ is an IS in $G$ $\iff$ for all distinct $u,v \in S$, $(u,v) \notin E$ $\iff$ for all distinct $u,v \in S$, $(u,v) \in \bar{E}$ $\iff$ $S$ is a clique in $\bar{G}$. $\square$

Theorem. Clique is NP-complete.

Proof. Clique $\in$ NP (shown above). For NP-hardness: given any instance $(G, k)$ of Independent Set, output $(\bar{G}, k)$ as the Clique instance. This reduction runs in $O(V^2)$ time. By the key observation, $G$ has an IS of size $k$ $\iff$ $\bar{G}$ has a clique of size $k$. Since Independent Set is NP-complete, so is Clique. $\square$

Example. The graph $G$ below (left) has edges ${1\text{-}2,\,2\text{-}3,\,3\text{-}4,\,4\text{-}5,\,2\text{-}4,\,1\text{-}4}$. The set ${1,3,5}$ (yellow) is an IS of size 3: none of those pairs share an edge. In the complement $\bar{G}$ (right), the missing edges ${1\text{-}3,\,1\text{-}5,\,3\text{-}5}$ are now present, making ${1,3,5}$ a 3-clique.

The three thick blue edges form the clique ${1,3,5}$ in $\bar{G}$, corresponding exactly to the three non-edges of the IS in $G$.

Vertex Cover

Definition (Vertex Cover). A vertex cover of $G = (V, E)$ is a set $S \subseteq V$ such that every edge has at least one endpoint in $S$:

\[\forall\,(u,v) \in E,\quad u \in S \;\text{or}\; v \in S.\]

The Vertex Cover decision problem asks: given $G$ and an integer $k$, does $G$ have a vertex cover of size $\le k$?

Vertex Cover is in NP: given a set $S$ as a certificate, verify $\lvert S \rvert \le k$ and scan all edges in $O(V + E)$ time.

Reduction: Independent Set $\le_p$ Vertex Cover

Key observation. Let $n = \lvert V \rvert$. A set $S \subseteq V$ is an independent set in $G$ $\iff$ $V \setminus S$ is a vertex cover of $G$.

Proof.

$(\Rightarrow)$ Let $S$ be an IS. For any edge $(u,v) \in E$, since $S$ is independent, $u$ and $v$ are not both in $S$, so at least one belongs to $V \setminus S$. Hence $V \setminus S$ covers every edge.

$(\Leftarrow)$ Let $C = V \setminus S$ be a vertex cover. If some $u,v \in S$ had $(u,v) \in E$, then neither endpoint would be in $C$, contradicting that $C$ is a cover. So $S$ is independent. $\square$

Theorem. Vertex Cover is NP-complete.

Proof. Vertex Cover $\in$ NP (shown above). For NP-hardness: given any instance $(G, k)$ of Independent Set (with $n = \lvert V \rvert$), output $(G,\, n - k)$ as the Vertex Cover instance — the same graph, target size $n - k$. This reduction runs in $O(1)$ additional time.

By the key observation, $G$ has an IS $S$ of size $k$ $\iff$ $V \setminus S$ is a vertex cover of size $n - k$ $\iff$ $G$ has a vertex cover of size $n - k$. Since Independent Set is NP-complete, so is Vertex Cover. $\square$

Example. The graph below has $5$ vertices and edges ${1\text{-}2,\,1\text{-}3,\,2\text{-}4,\,3\text{-}4,\,4\text{-}5}$. The vertex cover ${1,4}$ (red) has size $2$ and touches every edge. The complementary set ${2,3,5}$ (yellow) is an IS of size $3$: no two of them are adjacent.

Summary of Reductions So Far

The reductions form a chain rooted at 3-SAT (Cook-Levin):