the reduction to vertex cover, clique and independent set

Once SAT and 3-SAT are known to be hard, the next move is to spread that hardness to natural graph problems. Three classics fall together because they are secretly the same problem in three costumes: CLIQUE (find a set of vertices all mutually connected), INDEPENDENT SET (find a set of vertices with no edges between them), and VERTEX COVER (find a small set of vertices that touches every edge). This entry is the chain of reductions that proves all three NP-complete, starting from 3-SAT and turning a logical formula into a graph.

First, the easy ties between the three. In a graph G on n vertices, a set S is an INDEPENDENT SET if and only if S is a CLIQUE in the complement graph G' (where edges and non-edges are swapped) — so finding a k-independent-set in G equals finding a k-clique in G', a polynomial-time switch. And S is an independent set if and only if its complement V minus S is a VERTEX COVER: every edge has at least one endpoint outside S (since S has no internal edges), so V minus S covers all edges. Hence G has an independent set of size k exactly when G has a vertex cover of size n minus k. These give clique <=p independent-set <=p vertex-cover and back, so proving any ONE hard makes all three hard. Now the seed reduction, 3-SAT <=p clique (equivalently independent set). Given a 3-SAT formula with m clauses, build a graph with one vertex per literal-occurrence (3m vertices, grouped into m triangles-of-choices). Put an edge between two vertices whenever they are in DIFFERENT clauses AND are not contradictory (you never join x and not x). Then the formula is satisfiable if and only if this graph has a clique of size m: a clique must pick exactly one literal from each clause (different clauses) without contradiction, which is precisely a consistent choice of one true literal per clause — a satisfying assignment. The construction is polynomial, so 3-SAT <=p clique.

These reductions are the workhorses of the NP-complete zoo and a template for the gadget style of proof: each clause becomes a small local structure, edges encode the logical constraints, and a solution to the graph problem is wired to mean a satisfying assignment. Two honest reminders. The direction is fixed: we reduce 3-SAT INTO these problems to show THEY are hard, not the reverse. And note vertex cover is the 'small set' problem (minimise) while clique and independent set are 'large set' problems (maximise) — they trade places through complementation, which is why a clean fact like 'independent set of size k iff vertex cover of size n minus k' lets one reduction serve all three. The same hardness underlies their optimisation versions, which is why we turn to approximation algorithms (for example a 2-approximation for vertex cover) once exactness is hopeless.