A Bit of History
Stephen Cook published "The Complexity of Theorem-Proving Procedures" in 1971, proving that Boolean satisfiability (SAT) is NP-complete — the founding result of computational complexity theory. Leonid Levin, working independently in the Soviet Union under very different political and academic constraints, discovered an equivalent result around the same time, published in 1973 — the theorem is now properly called the Cook-Levin theorem in recognition of both. The very next year, Richard Karp (whose name recurs throughout this series, from Edmonds-Karp to Held-Karp) published "Reducibility Among Combinatorial Problems" in 1972, showing 21 fundamental combinatorial problems — many of them graph problems already met in this series — are all NP-complete, cementing the theory's practical relevance to real algorithmic questions almost immediately.
NP-Hardness of Graph Problems
A problem is in NP if a proposed solution can be verified quickly (in polynomial time), even if finding one might be hard. A problem is NP-complete if it is in NP and every other NP problem can be efficiently transformed ("reduced") into it — meaning an efficient algorithm for one NP-complete problem would efficiently solve all of them, and all currently known algorithms take at best exponential-ish worst-case time. Whether \(P = NP\) (whether every NP-complete problem secretly has a polynomial-time algorithm humanity simply hasn't found yet) remains the most famous open problem in computer science.
Karp's 21 NP-Complete Problems
Several of Karp's original 21 problems are graph problems this series has directly encountered:
- Hamiltonian Cycle (Part 12) — deciding whether a Hamiltonian cycle exists is NP-complete, in sharp contrast to the Eulerian circuit case, which Hierholzer's algorithm solves in linear time. This single contrast is one of the most-cited examples in complexity theory of how superficially similar problems can have wildly different difficulty.
- Graph Coloring (deciding if a graph is 3-colorable, generalizing Part 13) — NP-complete, even though 2-colorability (bipartiteness) is solvable in linear time via BFS.
- Clique (deciding whether a graph contains a complete subgraph of a given size) — NP-complete, and closely tied to the independent set and vertex cover problems by simple graph-complement reductions.
- Vertex Cover (finding the smallest set of vertices touching every edge) — NP-complete, though it admits a simple factor-2 approximation and is famously fixed-parameter tractable in the cover size (connecting to treewidth ideas from Part 18).
The Traveling Salesman Problem (Part 14) is likewise NP-hard (its decision version, "is there a tour of cost at most \(k\)", is NP-complete), directly motivating the exact-but-exponential Held-Karp algorithm and the polynomial-but-approximate Christofides algorithm from recent deep dives.
Matroid Theory
Hassler Whitney (already met in Part 17 for planar straight-line embeddings) introduced matroids in a 1935 paper, abstracting the essential combinatorial structure shared by both linear independence in vector spaces and forest-formation in graphs. A matroid is a pair \((E, \mathcal{I})\) — a ground set \(E\) and a collection \(\mathcal{I}\) of "independent" subsets — satisfying simple axioms (every subset of an independent set is independent; independent sets can always be extended by one element if a larger independent set exists).
Key Insight
The edge sets of forests in a graph form a matroid (the "graphic matroid") — and the reason Kruskal's and Prim's greedy MST algorithms work correctly is a special case of a much more general fact: the greedy algorithm always finds an optimal solution on any matroid. This single abstract theorem, due substantially to Jack Edmonds (of Blossom Algorithm fame, again), explains why so many seemingly-different greedy graph algorithms all happen to be correct.
Edmonds also developed a polynomial-time matroid intersection algorithm, finding the largest common independent set between two matroids simultaneously — a surprisingly powerful unifying framework capturing bipartite matching, arborescence-finding, and other problems as special cases, all solvable in polynomial time despite looking combinatorially quite different on the surface.
Approximation Algorithms
Since exact polynomial-time algorithms for NP-hard problems are not believed to exist, approximation algorithms trade exactness for guaranteed speed, with a provable bound on how far from optimal the answer can be — exactly the strategy already seen with Christofides' 3/2-approximation for metric TSP. Formal categories include:
- Constant-factor approximation: guarantees within some fixed multiplicative factor of optimal (e.g., Christofides' 3/2, or the simple factor-2 vertex cover approximation).
- PTAS (Polynomial-Time Approximation Scheme): for any desired accuracy \(\epsilon > 0\), produces a \((1+\epsilon)\)-approximation in time polynomial in the input size (though possibly exponential in \(1/\epsilon\)).
- FPTAS (Fully Polynomial-Time Approximation Scheme): the strongest guarantee — polynomial in both the input size and \(1/\epsilon\).
Not every NP-hard problem admits even a constant-factor approximation — general TSP (without the triangle inequality) provably cannot be approximated to any constant factor in polynomial time unless \(P=NP\), since arbitrarily bad "gadget" instances can always be constructed to defeat any proposed approximation ratio.
Real-World Applications
Chip Design & Register Allocation Reductions
Compiler register allocation (previewed as a graph-coloring application in Part 13) and VLSI chip placement (previewed for planarity in Part 17) are both, at their core, NP-hard graph problems in disguise — practical compilers and chip design tools do not solve them exactly, instead relying on carefully tuned heuristics and approximation algorithms whose worst-case guarantees come directly from the theory in this part, accepting occasionally suboptimal results in exchange for feasible runtimes on real, large-scale hardware designs.
Exercises
- Explain why "is there a Hamiltonian cycle in this graph" is in NP (i.e., why a proposed cycle can be verified quickly), even though finding one appears to require exponential search.
- Verify the matroid axioms hold for the graphic matroid of a small graph, by checking that every subset of a forest is itself a forest, and that any non-maximal forest can be extended by adding one more edge.
- Explain in your own words why the factor-2 vertex cover approximation (take both endpoints of every edge in a maximal matching) is guaranteed to never be more than twice the optimal cover size.
- Challenge: Research why general (non-metric) TSP cannot be approximated to any constant factor in polynomial time unless \(P=NP\), by looking up the "gadget" reduction argument from an NP-hard problem like Hamiltonian Cycle.
Conclusion & Next Steps
Complexity theory explains why so many algorithms in this series settled for heuristics or approximations rather than exact solutions — and matroid theory reveals the surprising unity behind why greedy algorithms like Kruskal's and Prim's work at all. The series now turns to how graph algorithms scale to genuinely massive, real-world data — data too large to fit on one machine, or arriving too fast to store in full.
Next in the Series
In Part 23: Modern Graph Algorithms — Dynamic, Streaming & Distributed, we'll explore how graph algorithms adapt to massive, changing, and distributed data.