Part 22: Complexity, Approximation & Combinatorial Optimization

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. Whether \(P = NP\) remains the most famous open problem in computer science.

Four Labels, Four Different Claims

The names are easy to blur together, so separate the question each label answers. Complexity classes are mostly discussed for decision problems — yes/no questions. An optimization problem such as "find the smallest vertex cover" is usually called NP-hard, while its threshold decision version — "is there a vertex cover of size at most \(k\)?" — can be NP-complete.

Reductions: How Hardness Moves Between Problems

A polynomial-time reduction \(A \le_p B\) is an efficient translator: it converts every instance of problem \(A\) into an instance of problem \(B\) so that solving the translated instance answers the original question. The direction matters enormously. To prove a new problem \(B\) is hard, start from a problem \(A\) already known to be hard and show \(A \le_p B\).

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 introduced matroids in 1935, abstracting the essential combinatorial structure shared by linear independence in vector spaces and cycle-free edge sets in graphs. A matroid is a pair \((E, \mathcal{I})\): a ground set \(E\) and a family \(\mathcal{I}\) of subsets declared "independent." The power comes from three compact rules.

The first two say independence is downward-closed. The third — the exchange axiom — is the real engine: if one independent solution is smaller than another, there is always some element from the larger one that safely extends the smaller one. That “you can always make locally safe progress” property is exactly what greedy algorithms need.

Why Greedy Becomes Universally Safe

For a weighted matroid, the standard greedy algorithm — process elements from best weight to worst and keep an element whenever independence is preserved — produces an optimal basis. Kruskal’s MST algorithm is exactly this theorem applied to the graphic matroid: sort edges by increasing weight and keep an edge when it does not create a cycle.

Edmonds also developed polynomial-time matroid intersection algorithms, which seek a largest set independent in two matroids at once. This creates a powerful unifying framework for problems that look unrelated at first glance.

Approximation Algorithms

Since exact polynomial-time algorithms for NP-hard problems are not believed to exist, approximation algorithms trade exactness for speed while keeping a mathematical contract on solution quality. That contract is what separates an approximation algorithm from a heuristic: a heuristic may work very well in practice; an approximation algorithm comes with a worst-case guarantee.

Approximation Ratios: Turn “Pretty Good” into an Inequality

For a minimization problem, an \(\alpha\)-approximation guarantees that the algorithm’s cost is at most \(\alpha\) times optimal. For a maximization problem, the direction reverses.

Formal approximation families include:

• Constant-factor approximation: guarantees within a fixed factor of optimal, such as factor 2 for the vertex-cover method above or \(3/2\) for Christofides on metric TSP.
• PTAS (Polynomial-Time Approximation Scheme): for any desired accuracy \(\epsilon>0\), produces a \((1+\epsilon)\)-approximation in time polynomial in the input size for each fixed \(\epsilon\), though the dependence on \(1/\epsilon\) may be very expensive.
• FPTAS (Fully Polynomial-Time Approximation Scheme): 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 cannot be approximated within any fixed constant factor in polynomial time unless \(P=NP\). Approximation itself therefore has a complexity theory: some problems are hard to solve exactly but easy to approximate; others remain resistant even when we relax optimality.

When Exact Is Hard, Change the Question You Ask

NP-hardness is not a command to give up. It tells you which escape hatches to look for: small inputs, special graph structure, a small parameter, an approximation guarantee, or a heuristic that performs well empirically.

Fixed-parameter tractability is especially useful when a natural parameter \(k\) is small even though the graph itself is large. Vertex Cover parameterized by solution size is a classic example: the exponential dependence can be isolated in \(k\) while the dependence on the full input remains polynomial.

Real-World Applications

Exercises

1. 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.
2. 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.
3. 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.
4. 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.