Classic NP-Complete Problems: Clique and Vertex Cover

A clique in an undirected graph $G = (V,E)$ is a subset $C \subseteq V$ such that every two distinct vertices in $C$ are joined by an edge. The Clique problem, as a decision problem, asks: given $G$ and an integer $k$, does $G$ contain a clique of size at least $k$? A vertex cover is a subset $S \subseteq V$ such that every edge of $G$ has at least one endpoint in $S$. The Vertex Cover problem asks: given $G$ and integer $k$, is there a vertex cover of size at most $k$? Both problems are phrased as decision problems (yes/no) rather than optimization problems, which is the standard convention in complexity theory — it lets us compare them cleanly against other decision problems like 3-SAT via Polynomial-Time Mapping Reductions. Recall that a reduction $f$ from language $A$ to language $B$, written $A \le_p B$, is a polynomial-time computable function such that $x \in A \iff f(x) \in B$. If $A$ is NP-hard and $A \le_p B$ with $B \in$ NP, then $B$ is NP-complete. The Cook-Levin Theorem establishes this hardness seed: SAT (and its restricted form 3-SAT, where every clause has exactly three literals) is NP-complete, because a nondeterministic Turing machine's computation can be encoded as a Boolean formula whose satisfying assignments correspond exactly to accepting computation histories. The strategy here is a two-step relay. First we reduce 3-SAT to Clique directly, translating the local structure of a 3-CNF formula (three literals per clause, at most one satisfied literal needed per clause, no two contradictory literals both true) into the local structure of a graph (edges represent "compatible," non-edges represent "conflicting" or "same clause"). Second, we show Clique and Vertex Cover are two views of the same combinatorial fact by passing to the graph complement — no simulation of computation is needed here, just a one-line algebraic identity relating cliques and covers.

Reduction 1: 3-SAT ≤p Clique. Let $\varphi = C_1 \wedge C_2 \wedge \cdots \wedge C_k$ be a 3-CNF formula with each clause $C_i = (\ell_{i,1} \vee \ell_{i,2} \vee \ell_{i,3})$, literals over variables $x_1, \dots, x_n$. Build a graph $G_\varphi$ as follows. ``` function REDUCE_3SAT_TO_CLIQUE(phi):

# phi has clauses C_1, ..., C_k, each with 3 literals V = {} for i in 1..k: for j in 1..3: create vertex v[i][j] labeled with literal l[i][j] add v[i][j] to V E = {} for i in 1..k: for j in 1..3: for i' in 1..k, i' != i: for j' in 1..3: l = label(v[i][j]) l' = label(v[i'][j']) if l is not the negation of l': add edge (v[i][j], v[i'][j']) to E G = (V, E) return (G, k) # ask: does G have a clique of size k? ``` Two vertices are connected exactly when they come from different clauses and their literals are not negations of each other (they might even be the same literal — that is fine, both can be true together). Vertices within the same clause are never connected, since a clause only needs one true literal, and we do not want to be forced to pick more than one vertex per clause.

Reduction 2: Clique ≤p Vertex Cover (and the reverse). The key fact is purely graph-theoretic and needs no gadget construction, only the notion of the complement graph $\bar{G} = (V, \bar{E})$, where $\bar{E}$ contains exactly the pairs not in $E$. ``` function REDUCE_CLIQUE_TO_VERTEX_COVER(G, k): n = |V(G)| Gbar = complement of G # (u,v) in Gbar iff (u,v) not in E(G) return (Gbar, n - k) # ask: does Gbar have a vertex cover of size n-k? ``` The same construction run in reverse (complementing again) reduces Vertex Cover to Clique, since $\overline{\bar{G}} = G$ and $n - (n-k) = k$. So the two problems are polynomial-time equivalent, not just each reducible to the other.

The pseudocode and figure describe the forward direction (3-SAT to Clique); the size parameter $k$ is set to the number of clauses, since a clique must pick exactly one vertex per clause block (no two vertices in the same block are ever adjacent) to reach size $k$.

Membership in NP. Both Clique and Vertex Cover are in NP. A certificate for Clique is the subset $C$ of size $k$; verification checks all $\binom{k}{2}$ pairs for edges, which takes $O(k^2)$ time, polynomial in the input size. A certificate for Vertex Cover is the subset $S$ of size $k$; verification scans every edge (at most $O(n^2)$ of them) and checks that at least one endpoint lies in $S$, also polynomial.

Correctness of 3-SAT ≤p Clique. Let $\varphi$ have $k$ clauses. We claim $\varphi$ is satisfiable iff $G_\varphi$ has a clique of size $k$. ($\Rightarrow$) Suppose assignment $a$ satisfies $\varphi$. Each clause $C_i$ has at least one literal made true by $a$; pick one such literal per clause and call its vertex $v_i$. The set $\{v_1, \dots, v_k\}$ has exactly one vertex per clause block, so no two of them are in the same block. For any $i \ne i'$, the literals at $v_i$ and $v_{i'}$ are both true under $a$, so they cannot be negations of each other (a variable and its negation cannot both be true). By construction there is therefore an edge between $v_i$ and $v_{i'}$. Hence $\{v_1,\dots,v_k\}$ is a clique of size $k$. ($\Leftarrow$) Suppose $G_\varphi$ has a clique $C$ of size $k$. Since vertices within one clause block are pairwise non-adjacent, $C$ can contain at most one vertex from each of the $k$ blocks; having size $k$ forces exactly one vertex per block. Define an assignment $a$: for each variable $x$, if some vertex in $C$ is labeled $x$, set $x = \text{true}$; if some vertex in $C$ is labeled $\neg x$, set $x = \text{false}$; set unconstrained variables arbitrarily. This is well-defined because $C$ is a clique: if $C$ contained both an $x$-vertex and a $\neg x$-vertex, they would (by construction) have no edge between them, contradicting that $C$ is a clique. Since every clause block contributes one vertex to $C$, every clause has a literal set true by $a$, so $a$ satisfies $\varphi$.

Polynomial-time computability of the reduction. $G_\varphi$ has exactly $3k$ vertices and at most $\binom{3k}{2} = O(k^2)$ candidate edges, each checked in constant time against the negation condition. The whole construction runs in $O(k^2)$ time and produces an instance of size polynomial in $|\varphi|$, satisfying the definition of a polynomial-time mapping reduction.

Correctness of Clique ↔ Vertex Cover. This rests on one identity: for any graph $H = (V,E)$ and subset $S \subseteq V$,

Proof. $S$ is a clique in $H$ means every pair $u,v \in S$ satisfies $(u,v) \in E(H)$, equivalently $(u,v) \notin E(\bar H)$. So $\bar H$ has no edge with both endpoints in $S$, meaning every edge of $\bar H$ has at least one endpoint outside $S$, i.e. in $V \setminus S$. That is precisely the statement that $V \setminus S$ covers every edge of $\bar H$. Each step is reversible (an "iff" throughout), so the equivalence holds in both directions. $\blacksquare$ Applying this with $H = G$ and $|S| = k$: $G$ has a $k$-clique iff $\bar G$ has a vertex cover of size $n - k$. This is exactly what the reduction computes, and running it on $(\bar G, n-k)$ recovers $(G, k)$, giving the reverse reduction for free. Complementing a graph takes $O(n^2)$ time (flip every possible pair's edge status), so the reduction is polynomial.

Complexity summary.

Because NP-completeness only asserts no known polynomial algorithm and NP-hardness, best-known exact algorithms for both problems remain exponential in the worst case — brute force over all $\binom{n}{k}$ subsets, or smarter branch-and-bound / treewidth-based methods that still blow up on adversarial graphs. Both problems do admit useful tradeoffs: Vertex Cover has a simple factor-2 polynomial-time approximation (repeatedly pick both endpoints of an uncovered edge), and a fixed-parameter-tractable algorithm running in $O(1.2^k \cdot n)$ time via kernelization, exponential only in the parameter $k$, not in $n$. Clique has no such approximation guarantee under standard complexity assumptions — approximating the maximum clique size within any polynomial factor is itself NP-hard, which is a notably harsher inapproximability landscape than Vertex Cover's.

Take $\varphi = (x_1 \vee x_2 \vee \neg x_3) \wedge (\neg x_1 \vee x_2 \vee x_3) \wedge (x_1 \vee \neg x_2 \vee x_3)$, matching the figure. We build $G_\varphi$ with $3 \times 3 = 9$ vertices and ask for a clique of size $k = 3$.

Try assignment $x_1 = x_2 = x_3 = \text{true}$. Check each clause: $C_1$ is satisfied by $x_1$ (or $x_2$), $C_2$ is satisfied by $x_2$ (or $x_3$), $C_3$ is satisfied by $x_1$ (or $x_3$). All three clauses are satisfied, so $\varphi$ is satisfiable. Following the forward direction of the proof, pick one true literal's vertex per clause: $v_{1,1}$ ($x_1$), $v_{2,2}$ ($x_2$), $v_{3,3}$ ($x_3$). Check pairwise edges:

• $v_{1,1}$ ($x_1$) and $v_{2,2}$ ($x_2$): different clauses, and $x_2$ is not $\neg x_1$, so edge exists.
• $v_{2,2}$ ($x_2$) and $v_{3,3}$ ($x_3$): different clauses, $x_3$ is not $\neg x_2$, so edge exists.
• $v_{1,1}$ ($x_1$) and $v_{3,3}$ ($x_3$): different clauses, $x_3$ is not $\neg x_1$, so edge exists.

All three pairs are adjacent, so $\{v_{1,1}, v_{2,2}, v_{3,3}\}$ is a 3-clique, exactly as the reconstruction procedure claims — matching the green triangle in the figure. Now push this graph through the second reduction. With $n = 9$ vertices and $k = 3$, the Vertex Cover instance is $(\bar{G_\varphi},\, 9 - 3 = 6)$: does the complement graph have a vertex cover of size 6? By the equivalence proved above, $V \setminus \{v_{1,1}, v_{2,2}, v_{3,3}\}$ — the other 6 vertices — must be a vertex cover of $\bar{G_\varphi}$. Indeed: any edge of $\bar{G_\varphi}$ is a non-edge of $G_\varphi$, and since $\{v_{1,1},v_{2,2},v_{3,3}\}$ is a clique in $G_\varphi$ (all pairs among them are edges in $G_\varphi$), no edge of $\bar{G_\varphi}$ can have both endpoints in that triple — so every $\bar{G_\varphi}$-edge touches the remaining 6 vertices, confirming the cover.

The classification of Clique and Vertex Cover as NP-complete traces back to the founding wave of complexity theory that formalized what it means for a problem to be "as hard as any problem checkable in polynomial time."

Vertex Cover's structure appears directly in network monitoring: choosing the minimum set of routers or sensors so that every network link is observed by at least one endpoint is exactly a vertex cover instance, and the 2-approximation algorithm is used in practice when exact solutions are infeasible. Clique detection underpins social-network analysis (finding tightly-knit communities), bioinformatics (protein interaction clusters, where mutually-interacting proteins form cliques in interaction graphs), and computer vision (matching feature correspondences that must be mutually consistent). Scheduling systems that need to find the maximum set of pairwise-compatible tasks are solving Clique on a compatibility graph, and register allocation in compilers historically used graph-coloring formulations closely related to these problems. The reduction techniques themselves — building a gadget per clause and enforcing exactly-one-per-gadget selection — are reused throughout complexity theory, including in reductions to Hamiltonian Path and Circuit Problems, where similar "force exactly one choice per structural unit" gadgets encode computation into path-existence questions.

Ask the tutor: Can you show how the same clause-gadget technique extends to reduce 3-SAT directly to the Hamiltonian Path problem?