---
title: Coping with NP-Hardness
module: Intractability
moduleNumber: 12
lessonNumber: 3
order: 1203
summary: |
  An $\mathsf{NP}$-hardness proof rules out an exact polynomial-time algorithm,
  not the need for answers. This lesson surveys four practical responses to
  hardness: approximation algorithms with a provable ratio (worked through a
  2-approximation for vertex cover), heuristics and local search, exact
  exponential methods like branch and bound, and exploiting special structure
  in the instances you actually face.
topics: [Approximation, Heuristics]
sources:
  - book: CLRS
    ref: "Ch. 35 — Approximation Algorithms"
  - book: Skiena
    ref: "§11 — NP-Completeness; Heuristics"
  - book: Erickson
    ref: "Ch. 12 — NP-Hardness"
practice:
  - title: 'Combination Sum'
    slug: combination-sum
    difficulty: Medium
  - title: 'Word Search'
    slug: word-search
    difficulty: Medium
  - title: 'Matchsticks to Square'
    slug: matchsticks-to-square
    difficulty: Medium
  - title: 'Maximum Score Words Formed by Letters'
    slug: maximum-score-words-formed-by-letters
    difficulty: Hard
---

This is the capstone of the course, so let us first take stock of the tools we
have assembled. Almost every algorithm we built fell under a handful of
**paradigms**, recurring structures that apply across problems:

- **Divide and conquer.** Split, recurse, combine; analyzed by recurrences and
  the master theorem (merge sort, counting inversions, closest points, Karatsuba,
  Strassen).
- **Dynamic programming.** Tabulate overlapping subproblems (LCS, interval
  scheduling, Bellman–Ford, Floyd–Warshall, [knapsack](/algorithms/dynamic-programming/knapsack), subset-sum).
- **[Greedy](/algorithms/greedy/the-greedy-method).** Commit to a locally best choice and prove it is safe (Huffman,
  Dijkstra, Prim, Kruskal; Dijkstra and Prim share the _same_ greedy
  skeleton, differing only in the priority key).
- **Graph methods.** BFS, DFS, topological sort, strongly connected components,
  and the shortest-path and [spanning-tree](/algorithms/graphs/minimum-spanning-trees) algorithms built atop them.
- **Network flow.** Max-flow / min-cut (Ford–Fulkerson, Edmonds–Karp) as a
  modeling tool covering matching, scheduling, and connectivity problems.
- **[Reductions](/algorithms/intractability/p-np-reductions) and [$\mathsf{NP}$-completeness](/algorithms/intractability/np-completeness)**, the meta-tool: relate one
  problem to another, transferring either an algorithm or a hardness proof.

This lesson builds on that last paradigm. Suppose you have
followed the recipe from the previous lesson and proved that the problem on your
desk is $\mathsf{NP}$-hard. This is genuine progress: you now know not to waste
months hunting for a fast exact algorithm that almost certainly does not exist.
But the problem still has to be solved. $\mathsf{NP}$-hardness is a
statement about the _worst case over all instances_; it does not forbid doing
well on the instances you actually meet, or doing _nearly_ as well as optimal, or
doing exactly as well but slowly.

There are four honest ways to cope, and a well-designed system often blends
them. We can **approximate**: settle for a solution provably close to optimal.
We can use **heuristics**, methods that work well in practice without
guarantees. We can pay for an **exact exponential** algorithm that is merely
_smart_ about its exponential search. Or we can exploit **special structure**
in our instances. We take each in turn.

The decision tree below summarizes the choices:
_first_ ask whether the problem is even hard; only the rightmost branch forces
the compromises of this lesson.

$$
% caption: Decision tree choosing a coping strategy for a possibly NP-hard problem.
\begin{tikzpicture}[
    >=Stealth, node distance=9mm,
    q/.style={draw, minimum height=17mm, inner sep=4pt,
              align=center, font=\small, very thick},
    a/.style={draw, minimum height=17mm, inner sep=4pt,
              align=center, font=\small},
    lbl/.style={font=\scriptsize}]
  \node (np) [q] {Is it\\$\mathsf{NP}$-hard?};
  \node (poly) [a, left=18mm of np] {Use a known\\poly-time\\algorithm};
  \node (struct) [q, below=12mm of np] {Special\\structure?};
  \node (exploit) [a, right=16mm of struct] {Exploit it:\\tree / planar,\\small $k$, pseudo-poly};
  \node (need) [q, below=12mm of struct] {Need a\\guarantee?};
  \node (approx) [a, left=16mm of need] {Approximation\\algorithm\\(ratio bound)};
  \node (exact) [q, below=12mm of need] {Exact\\optimum?};
  \node (bnb) [a, right=16mm of exact] {Branch \&\\bound};
  \node (heur) [a, below=11mm of exact] {Heuristic /\\local search};
  \draw[->] (np) -- node[lbl, above] {no} (poly);
  \draw[->] (np) -- node[lbl, right] {yes} (struct);
  \draw[->] (struct) -- node[lbl, above] {yes} (exploit);
  \draw[->] (struct) -- node[lbl, right] {no} (need);
  \draw[->] (need) -- node[lbl, above] {yes} (approx);
  \draw[->] (need) -- node[lbl, right] {no} (exact);
  \draw[->] (exact) -- node[lbl, above] {yes} (bnb);
  \draw[->] (exact) -- node[lbl, right] {no} (heur);
\end{tikzpicture}
$$

## Approximation algorithms

The first response is to relax _optimality_ while
keeping a _guarantee_. An **approximation algorithm** runs in polynomial time
and returns a solution provably within a bounded factor of the best possible.

> **Definition ($\rho$-approximation).** For a minimization problem, an algorithm is a $\rho$-approximation (with
> $\rho \ge 1$) if, on every instance, it runs in polynomial time and returns a
> solution of cost $C$ satisfying
> $$ C \le \rho \cdot C^{\ast}, $$
> where $C^{\ast}$ is the cost of an optimal solution. The factor $\rho$ is the
> **approximation ratio**. (For a maximization problem the bound flips to $C
> \ge C^{*} / \rho$.)

A ratio of $\rho = 2$ means "never more than twice optimal": guaranteed, on
every input, with no exceptions. The subtlety is that we prove
this _without ever knowing $C^{\ast}$_. The proof almost always uses a **lower
bound**: find some quantity that provably under-estimates $C^{\ast}$, then show
the solution is not much bigger than _that_.

$$
% caption: A $\rho$-approximation pins the output cost $C$ into the band
%          $[C^{*}, \rho\, C^{*}]$ — proved via a lower bound $L \le C^{*}$.
\begin{tikzpicture}[>=Stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  \draw[->, thick] (0,0) -- (11,0);
  \node[anchor=north] at (11,-0.1) {cost};
  % lower bound L
  \node[circle, draw, fill=black!12, inner sep=1.6pt] (L) at (1.6,0) {};
  \node[anchor=south, font=\scriptsize] at (1.6,0.18) {$L$ (lower bound)};
  % optimum OPT
  \node[circle, draw, fill=black!12, inner sep=1.9pt] (C) at (4.2,0) {};
  \node[anchor=south, font=\footnotesize] at (4.2,0.18) {\texttt{OPT} (optimum)};
  % our output C
  \node[circle, draw=acc, fill=acc!15, very thick, inner sep=1.9pt] (Cout) at (7.6,0) {};
  \node[anchor=south, font=\scriptsize, text=acc] at (7.6,0.18) {$C$ (output)};
  % rho * OPT
  \node[circle, draw, inner sep=1.9pt] (R) at (9.4,0) {};
  \node[anchor=south, font=\footnotesize] at (9.4,0.18) {\texttt{r x OPT}};
  % feasible band bracket under axis
  \draw[acc, thick] (4.2,-0.45) -- (9.4,-0.45);
  \draw[acc] (4.2,-0.35) -- (4.2,-0.55);
  \draw[acc] (9.4,-0.35) -- (9.4,-0.55);
  \node[anchor=north, font=\scriptsize, text=acc] at (6.8,-0.6)
    {guaranteed band: \texttt{C at most r x OPT}};
  \node[anchor=north, font=\footnotesize] at (2.9,-0.6) {\texttt{L at most OPT} (unknown)};
\end{tikzpicture}
$$

### A worked example: 2-approximation for Vertex Cover

A **vertex cover** of a graph $G = (V, E)$ is a set of vertices touching every
edge: for each edge, at least one endpoint is chosen. $\textsc{Min-Vertex-Cover}$, the
problem of finding the smallest such set, is $\mathsf{NP}$-hard. Yet a
simple algorithm comes within a factor of $2$.

```algorithm
caption: $\textsc{Approx-Vertex-Cover}(G)$ — return a cover at most twice optimal
number: 1
$C \gets \emptyset$
$E' \gets E$ // working copy
while $E' \neq \emptyset$ do
  pick any edge $(u, v) \in E'$
  $C \gets C \cup \{u, v\}$ // take both endpoints
  remove from $E'$ every edge incident to $u$ or $v$
return $C$
```

The algorithm repeatedly picks an uncovered edge and adds _both_ its
endpoints to the cover. Taking both looks wasteful,
but it is what makes the analysis work.

> **Proof (correctness).** The loop continues until $E'$ is empty, i.e. until
> every edge is incident to some chosen vertex. So $C$ is a valid vertex cover.
> $\qed$

> **Theorem (Ratio).** $\textsc{Approx-Vertex-Cover}$ returns a cover $C$ with
> $|C| \le 2\,C^{\ast}$, where $C^{\ast}$ is the size of a minimum vertex cover.

> **Proof.** Let $M$ be the set of edges _picked_ in the loop (one per
> iteration). No two edges in $M$ share an endpoint: once we pick $(u,v)$, we
> delete every edge touching $u$ or $v$, so no later picked edge can reuse them.
> A set of edges sharing no endpoints is a **matching**. Now the two key facts:
>
> - Our cover has $|C| = 2|M|$, two fresh vertices per picked edge.
> - _Any_ vertex cover, including the optimal one, must contain at least one
>   endpoint of each edge in $M$; since those endpoints are all distinct, $C^{*}
>   \ge |M|$.
>
> Chaining these, $|C| = 2|M| \le 2\,C^{\ast}$. $\qed$

So $\textsc{Approx-Vertex-Cover}$ is a $2$-approximation.[^clrs-vc] We bounded
our output against $|M|$, a quantity that lower-bounds the unknown optimum — the
standard technique of approximation analysis. (Whether vertex cover admits a ratio
better than $2$ is a famous open question; under standard hardness
assumptions, no polynomial-time algorithm does substantially better.)

$$
% caption: $\textsc{Approx-Vertex-Cover}$: each picked matching edge (heavy) contributes
%          both endpoints (filled) to the cover, giving $|C| = 2|M| \le 2C^{*}$.
\begin{tikzpicture}[>=Stealth, font=\small,
    v/.style={circle, draw, inner sep=1.7pt, minimum size=5mm},
    cov/.style={circle, draw=acc, fill=acc!15, very thick, inner sep=1.7pt, minimum size=5mm}]
  \definecolor{acc}{HTML}{2348F2}
  \node[cov] (a) at (0,1.4) {$a$};
  \node[cov] (b) at (2,1.4) {$b$};
  \node[cov] (c) at (4,1.4) {$c$};
  \node[cov] (d) at (6,1.4) {$d$};
  \node[v]   (e) at (1,0) {$e$};
  \node[v]   (f) at (3,0) {$f$};
  \node[v]   (g) at (5,0) {$g$};
  % matching edges (heavy, accent)
  \draw[acc, very thick] (a)--(b);
  \draw[acc, very thick] (c)--(d);
  % other edges covered by the chosen endpoints
  \draw (a)--(e);
  \draw (b)--(f);
  \draw (c)--(f);
  \draw (c)--(g);
  \draw (d)--(g);
  \node[anchor=south, font=\scriptsize, text=acc, fill=white, inner sep=1.5pt] at (1,1.62) {$M$: edge 1};
  \node[anchor=south, font=\scriptsize, text=acc, fill=white, inner sep=1.5pt] at (5,1.62) {$M$: edge 2};
  \node[anchor=north, align=center, font=\scriptsize] at (3,-0.4)
    {cover \texttt{C = a,b,c,d}, size \texttt{2M = 4}; every edge touches a chosen vertex};
\end{tikzpicture}
$$

::impl{algo="approx_vertex_cover"}

Approximability varies widely across problems:

- Some problems admit a **polynomial-time approximation scheme** (PTAS): for any
  $\varepsilon > 0$ a $(1+\varepsilon)$-approximation in polynomial time: you
  can get as close to optimal as you like, paying in running time.
  **Euclidean TSP** and **Knapsack** are of this kind.[^clrs-ptas]
- Some have a fixed best-possible constant ratio, like vertex cover's $2$.
- Some are **inapproximable**: unless $\mathsf{P} = \mathsf{NP}$, no
  polynomial-time algorithm achieves _any_ constant ratio. **General TSP**
  (without triangle inequality) is the classic example: even approximating it
  within any factor is $\mathsf{NP}$-hard.

When the triangle inequality _does_ hold (the **metric** case), a
$2$-approximation follows from the [minimum spanning tree](/algorithms/graphs/minimum-spanning-trees): double every MST
edge to get an Eulerian multigraph, walk an Euler tour, and **shortcut** past
already-visited vertices. The shortcuts only shorten the walk (triangle
inequality), so the tour costs at most $2\,\text{MST} \le 2\,\text{OPT}$, since
the MST is no heavier than the optimal tour with one edge removed.

$$
% caption: Metric-TSP $2$-approximation: double the MST into an Euler tour, then shortcut
%          repeats; cost $\le 2\,\text{MST} \le 2\,\text{OPT}$.
\begin{tikzpicture}[>=Stealth, font=\small,
    v/.style={circle, draw, fill=black!6, inner sep=1.7pt, minimum size=5mm}]
  \definecolor{acc}{HTML}{2348F2}
  % left: MST
  \begin{scope}
    \node[v] (a) at (0,2) {$a$};
    \node[v] (b) at (1.6,2.4) {$b$};
    \node[v] (c) at (1.2,0.7) {$c$};
    \node[v] (d) at (2.8,1.2) {$d$};
    \node[v] (e) at (0.2,0.5) {$e$};
    \draw[acc, very thick] (a)--(b);
    \draw[acc, very thick] (a)--(c);
    \draw[acc, very thick] (c)--(d);
    \draw[acc, very thick] (a)--(e);
    \node[anchor=north, font=\scriptsize] at (1.3,-0.1) {MST $T$ (cost at most OPT)};
  \end{scope}
  % arrow
  \draw[->, thick] (3.4,1.3) -- node[above, font=\scriptsize]{double +} node[below, font=\scriptsize]{shortcut} (5.0,1.3);
  % right: shortcut tour
  \begin{scope}[shift={(5.6,0)}]
    \node[v] (a) at (0,2) {$a$};
    \node[v] (b) at (1.6,2.4) {$b$};
    \node[v] (c) at (1.2,0.7) {$c$};
    \node[v] (d) at (2.8,1.2) {$d$};
    \node[v] (e) at (0.2,0.5) {$e$};
    % a Hamiltonian cycle a-b-d-c-e-a
    \draw[acc, very thick] (a)--(b);
    \draw[acc, very thick] (b)--(d);
    \draw[acc, very thick] (d)--(c);
    \draw[acc, very thick] (c)--(e);
    \draw[acc, very thick] (e)--(a);
    \node[anchor=north, font=\scriptsize] at (1.3,-0.1) {tour (cost at most 2 OPT)};
  \end{scope}
\end{tikzpicture}
$$

::impl{algo="metric_tsp_approx"}

## Heuristics and local search

When a provable ratio is out of reach or simply unnecessary, we turn to
**heuristics**, strategies that are usually good but carry no worst-case
promise. The most general is **local search**: start from some feasible
solution and repeatedly apply a small modification, a _move_, that improves
the objective, stopping at a **local optimum** where no single move helps.

For the traveling salesman, the famous **2-opt** move deletes two edges of the
current tour and reconnects the pieces the other way; iterating it untangles
crossings and converges to short, though not always optimal, tours.

$$
% caption: A 2-opt move deletes two crossing edges (discarded, red) and reconnects the
%          four endpoints the other way, uncrossing the tour and shortening it.
\begin{tikzpicture}[>=Stealth, font=\small,
    v/.style={circle, draw, fill=black!6, inner sep=1.6pt, minimum size=4.5mm}]
  \definecolor{acc}{HTML}{2348F2}
  % left: crossing tour
  \begin{scope}
    \node[v] (a) at (0,2)   {$a$};
    \node[v] (b) at (2.2,2) {$b$};
    \node[v] (c) at (0,0)   {$c$};
    \node[v] (d) at (2.2,0) {$d$};
    % surrounding tour edges (kept)
    \draw[acc, very thick] (a) to[bend left=35] (b);
    \draw[acc, very thick] (c) to[bend right=35] (d);
    % the two edges that cross (to be deleted)
    \draw[red!75!black, very thick] (a) -- (d);
    \draw[red!75!black, very thick] (c) -- (b);
    \node[anchor=north, font=\scriptsize, text=red!75!black] at (1.1,-0.35)
      {delete the two crossing edges};
  \end{scope}
  \draw[->, thick] (3.1,1.0) -- node[above, font=\scriptsize]{2-opt} (4.5,1.0);
  % right: uncrossed tour
  \begin{scope}[shift={(5.4,0)}]
    \node[v] (a) at (0,2)   {$a$};
    \node[v] (b) at (2.2,2) {$b$};
    \node[v] (c) at (0,0)   {$c$};
    \node[v] (d) at (2.2,0) {$d$};
    \draw[acc, very thick] (a) to[bend left=35] (b);
    \draw[acc, very thick] (c) to[bend right=35] (d);
    % reconnected the other way (no crossing)
    \draw[acc, very thick] (a) -- (c);
    \draw[acc, very thick] (b) -- (d);
    \node[anchor=north, font=\scriptsize, text=acc] at (1.1,-0.35)
      {reconnect the other way: shorter};
  \end{scope}
\end{tikzpicture}
$$

::impl{algo="two_opt_tsp"}

Local
search has a characteristic failure mode: it can stall in a local optimum far
from the global one. The standard escapes are _metaheuristics_ that
occasionally accept worsening moves to climb out of bad valleys:

- **Simulated annealing** accepts uphill moves with a probability that cools
  over time, mimicking the physics of slowly freezing metal.
- **Tabu search** forbids recently-visited solutions to avoid cycling back.
- **Genetic algorithms** evolve a population of solutions by recombination and
  mutation.

$$
% caption: Local search descends to the nearest valley and stalls at a local optimum; a
%          metaheuristic must accept an uphill move to escape and reach the global
%          optimum.
\begin{tikzpicture}[>=Stealth, font=\small]
  \definecolor{acc}{HTML}{2348F2}
  % axes
  \draw[->] (0,0) -- (0,2.9) node[anchor=south east, font=\scriptsize] {cost};
  \draw[->] (0,0) -- (9.3,0) node[anchor=north east, font=\scriptsize] {solution space};
  % cost landscape with two controlled wells: shallow local well at x=2, deep global well at x=6.6
  \draw[thick]
    (0.5,2.3)
      .. controls (1.3,2.3) and (1.5,0.95) .. (2.0,0.95)   % into shallow local minimum
      .. controls (2.5,0.95) and (2.9,2.25) .. (3.7,2.25)  % up over the ridge
      .. controls (4.7,2.25) and (5.6,0.30) .. (6.6,0.30)  % down into deep global minimum
      .. controls (7.4,0.30) and (7.8,1.6) .. (8.6,1.7);   % back up on the right
  % local optimum marker, sitting in the shallow well
  \node[circle, draw, fill=black!12, inner sep=1.6pt] at (2.0,0.95) {};
  \draw[black] (1.7,2.28) -- (1.95,1.12);
  \node[anchor=south, font=\scriptsize, align=center] at (1.55,2.32)
    {local optimum\\(search stalls here)};
  % global optimum marker, in the deep well
  \node[circle, draw=acc, fill=acc!15, very thick, inner sep=1.7pt] at (6.6,0.30) {};
  \node[anchor=west, font=\scriptsize, text=acc, align=left] at (6.95,0.55)
    {global\\optimum};
  % escape arrow: uphill over the ridge toward the deeper well
  \draw[->, red!75!black, thick] (2.35,1.05) to[bend left=20] (4.05,1.55);
  \node[font=\scriptsize, text=red!75!black, align=center, anchor=south] at (3.5,1.75)
    {accept an uphill\\move to escape};
\end{tikzpicture}
$$

::impl{algo="simulated_annealing"}

Heuristics dominate industrial practice precisely because they are flexible
and fast. Their cost is the loss of guarantees: you rarely know how far from
optimal you landed. The honest practice, Skiena stresses, is to test against
known optima on small instances and against lower bounds on large ones.[^skiena-heur]

## Exact exponential methods: branch and bound

Sometimes you genuinely need the _optimal_ answer and the instances are small
enough to afford exponential time, provided it is spent wisely. Search the space
of solutions as a tree, **pruning** subtrees that provably cannot beat the best
solution found so far — this is **[branch and
bound](/algorithms/backtracking/branch-and-bound)**.

The method interleaves two operations. _Branching_ splits the problem into
subproblems (e.g. "vertex $v$ is in the cover" vs. "$v$ is out"), forming a
search tree. _Bounding_ computes, for each subproblem, an optimistic estimate,
a **bound**, on the best solution reachable within it. If that optimistic
estimate is already no better than the best complete solution we have already
found (the **incumbent**), the entire subtree is discarded unexplored.

> **Remark (The pruning rule).** For a minimization problem, maintain the incumbent cost
> $U$ (best solution so far). At a subproblem with optimistic lower bound $L$,
> if $L \ge U$, _prune_ — nothing in this subtree can improve on the incumbent.

The worst case is still exponential; branch and bound does not remove
$\mathsf{NP}$-hardness. But on real instances a good bound can prune away the
overwhelming majority of the tree, making problems with thousands of variables
routinely solvable. The quality of the bound is everything: a tight bound (often
from a relaxation such as linear programming) prunes aggressively; a loose one
leaves a near-complete exponential search. Modern integer-programming solvers
are highly engineered branch-and-bound implementations.

$$
% caption: Branch and bound: split on a variable, bound each subtree, and prune any whose
%          optimistic bound $L$ is no better than the incumbent $U$.
\begin{tikzpicture}[>=Stealth, font=\small,
    n/.style={circle, draw, minimum size=8mm, inner sep=1pt},
    pruned/.style={circle, draw=red!75!black, dashed, minimum size=8mm, inner sep=1pt, fill=red!18},
    keep/.style={circle, draw=acc, fill=acc!15, very thick, minimum size=8mm, inner sep=1pt}]
  \definecolor{acc}{HTML}{2348F2}
  \node[n] (r) at (0,2.6) {};
  \node[n] (l) at (-2.4,1.2) {};
  \node[n] (rr) at (2.4,1.2) {};
  \node[keep] (ll) at (-3.6,-0.2) {};
  \node[pruned] (lr) at (-1.2,-0.2) {};
  \node[n] (rl) at (1.2,-0.2) {};
  \node[pruned] (rrr) at (3.6,-0.2) {};
  \draw[->] (r) -- node[above left, font=\scriptsize]{$v=0$} (l);
  \draw[->] (r) -- node[above right, font=\scriptsize]{$v=1$} (rr);
  \draw[->] (l) -- (ll);
  \draw[->] (l) -- (lr);
  \draw[->] (rr) -- (rl);
  \draw[->] (rr) -- (rrr);
  \node[font=\scriptsize, text=acc, anchor=north] at (-3.6,-0.55) {incumbent $U$};
  \node[font=\footnotesize, text=red!75!black, anchor=north, align=center] at (-1.2,-0.55) {\texttt{L $\ge$ U}\\prune};
  \node[font=\footnotesize, text=red!75!black, anchor=north, align=center] at (3.6,-0.55) {\texttt{L $\ge$ U}\\prune};
  \node[font=\scriptsize, anchor=west] at (0.45,2.6) {root: all solutions};
\end{tikzpicture}
$$

::impl{algo="exact_vertex_cover"}

## Exploiting special structure

The final and most underrated strategy is to remember that
$\mathsf{NP}$-hardness is a worst case over _all_ inputs, and your inputs may
not be the worst. Many hard problems become _easy_ when restricted to the
structured instances that arise in practice.

- **Restricted graph classes.** Problems that are $\mathsf{NP}$-hard on general
  graphs frequently admit polynomial (even linear) algorithms on **trees**,
  on **bipartite** graphs, or on **planar** graphs. Independent Set, hard in
  general, falls to a simple greedy/dynamic program on trees.
- **Bounded parameters.** A problem may be solvable in time
  $f(k) \cdot n^{O(1)}$, where $k$ is some small parameter of the instance (the
  solution size, the treewidth, the number of constraints). The exponential
  blow-up is confined to $k$, so if $k$ is small the algorithm is fast. This is
  the domain of **fixed-parameter tractability**: Vertex Cover, for instance, is
  solvable in $O(2^{k} \cdot n)$ for covers of size $k$, practical whenever the
  cover is small even if the graph is huge.[^erickson-struct]
- **Pseudo-polynomial algorithms.** Numeric problems like $\textsc{Subset-Sum}$ and
  **Knapsack** have dynamic programs running in time polynomial in the
  _numeric values_, fast when the numbers are modest, exponential only because
  values can be exponentially large in their bit-length.

The lesson is to look hard at the instances you must actually solve before
declaring defeat. Hardness in the worst case is fully compatible with easiness
in your case.

::impl{algo="tree_independent_set,fpt_vertex_cover"}

## Parameterized complexity as its own theory

The "bounded parameters" idea above grew into a full
complexity theory, **parameterized complexity**, developed by Downey and Fellows in
the 1990s.[^df] It replaces the single input size $n$ with a pair $(n, k)$, where
$k$ is a chosen parameter, and asks for algorithms whose exponential cost is
confined to $k$. The central class is **FPT** (fixed-parameter tractable): problems
solvable in $f(k)\cdot n^{O(1)}$ for some function $f$. Vertex Cover's
$O(2^k\cdot n)$ puts it in FPT; the exponential in $k$ is unavoidable (the problem
is still $\mathsf{NP}$-hard), but it is isolated from $n$.

Two results make this more than a definition. The first is **kernelization**, a
provable form of preprocessing. A kernelization reduces an instance $(x, k)$ in
polynomial time to an equivalent instance whose _size is bounded by a function of
$k$ alone_ — for Vertex Cover, down to $O(k^2)$ vertices via the Buss reduction
(any vertex of degree $> k$ must be in every size-$k$ cover, so take it). After
kernelization the surviving core is small whenever $k$ is small, and brute force
finishes the job. A theorem ties the two ideas together: **a problem is in
FPT if and only if it has a kernel.**

$$
% caption: Kernelization shrinks a large instance to a core of size bounded by $k$ in
%          polynomial time; brute force then finishes on the small kernel.
\begin{tikzpicture}[>=Stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \draw[thick] (0,0) rectangle (3.4,2.0);
  \node at (1.7,2.35) {instance, size $n$};
  \draw[acc, thick, ->] (3.7,1.0) -- node[above, font=\scriptsize]{poly-time} node[below, font=\scriptsize]{kernelize} (6.1,1.0);
  \draw[thick, draw=acc, fill=acc!12] (6.3,0.55) rectangle (7.5,1.45);
  \node[acc] at (6.9,1.75) {kernel, size $g(k)$};
  \draw[red!75!black, thick, ->] (7.8,1.0) -- node[above, font=\scriptsize]{brute force} (10.0,1.0);
  \node[red!75!black, anchor=west] at (10.1,1.0) {answer};
\end{tikzpicture}
$$

The second result is a **hardness theory** for parameters. Not every parameterized
problem is FPT; the $\mathsf{W}$-hierarchy ($\mathsf{FPT} \subseteq \mathsf{W}[1]
\subseteq \mathsf{W}[2] \subseteq \cdots$) plays the role that $\mathsf{NP}$ plays
for ordinary complexity. **Clique parameterized by solution size** is
$\mathsf{W}[1]$-hard, which is strong evidence it has _no_ $f(k)\cdot n^{O(1)}$
algorithm — its best known algorithms are $n^{O(k)}$, with the exponent growing in
$k$. So parameterized complexity draws a second, finer tractability line right
through the class of $\mathsf{NP}$-hard problems: Vertex Cover and Clique are both
$\mathsf{NP}$-complete and inter-reducible, yet one is FPT and the other is
$\mathsf{W}[1]$-hard. The choice of parameter decides which side a problem
lands on.

## Choosing a strategy

These responses are not rivals so much as a toolkit; the right choice depends on
what you can tolerate.

- Need a _guarantee_ and can accept "near-optimal"? Reach for an
  **approximation algorithm**.
- Need _speed_ and _flexibility_ and can live without guarantees? Use a
  **heuristic** or **local search**, validated empirically.
- Need the _exact_ optimum on instances of modest size? Invest in **branch and
  bound** with the tightest bound you can compute.
- Do your real instances have _structure_, such as small parameters, special graph
  shape, or modest numbers? **Exploit it**, possibly turning the problem
  polynomial outright.

## Final thoughts

Looking back, the course covered three things: how to _analyze_
(asymptotics, recurrences, invariants), how to _design_ across a small repertoire of
paradigms (divide and conquer, dynamic programming, greedy, graph search, network
flow), and how to _recognize the limits of design_ through reductions and
$\mathsf{NP}$-completeness. When the limit is
real, change the question: trade exactness, optimality,
or generality for tractability, and state clearly
what was given up.

The paradigms compose. A branch-and-bound solver gets its bound from a relaxation
(often linear programming); an approximation proof rests on a combinatorial
lower bound like a matching; a special-case algorithm is frequently just dynamic
programming rediscovered on a tree. The reduction habit — _map my problem onto one
I already understand_ — is the same whether you are proving hardness or
borrowing an algorithm. A few paradigms, understood deeply, cover problems
you have never seen.

Natural sequels to this material are advanced algorithms and data
structures (Fibonacci heaps, the engineering behind Dijkstra/Prim and disjoint-set
union), complexity and computability theory (the formal machinery beneath
$\mathsf{P}$ and $\mathsf{NP}$), and the specialized branches (randomized,
streaming, distributed, and geometric algorithms) where each of the paradigms
above reappears in a new guise.

## Takeaways

- $\mathsf{NP}$-hardness rules out a fast exact algorithm in the _worst case_,
  not useful answers in practice. There are four honest responses.
- An **approximation algorithm** trades optimality for a _provable ratio_ $C \le
  \rho\, C^{*}$. The proofs lean on a **lower bound** for the unknown optimum,
  as in the **2-approximation for vertex cover**, which takes both endpoints of
  a maximal matching, giving $|C| = 2|M| \le 2C^{\ast}$.
- **Heuristics** and **local search** (2-opt, simulated annealing, tabu search)
  are fast and flexible but unguaranteed; validate them empirically.
- **Branch and bound** finds the exact optimum by searching a tree and
  **pruning** subtrees whose optimistic bound cannot beat the incumbent; still
  exponential in the worst case, often fast in practice.
- **Special structure** (trees, planar or bounded-treewidth graphs, small
  parameters, modest numeric values) frequently turns a worst-case-hard problem
  tractable on the instances you actually face.
- **Capstone view.** The course is a small kit of composable paradigms (divide
  and conquer, dynamic programming, greedy, graph methods, network flow) bounded
  by reductions and $\mathsf{NP}$-completeness. When hardness is real, you change
  the question (approximation, heuristic, exact-but-exponential, special case)
  rather than abandon it.

[^clrs-vc]: **CLRS**, Ch. 35 — Approximation Algorithms (§35.1): the $2$-approximation for vertex cover via a maximal matching lower bound, $|C| = 2|M| \le 2C^{\ast}$.
[^clrs-ptas]: **CLRS**, Ch. 35 — Approximation Algorithms: polynomial-time approximation schemes (PTAS), including Knapsack and Euclidean TSP.
[^skiena-heur]: **Skiena**, §11 — NP-Completeness; Heuristics: local search and metaheuristics, and validating unguaranteed heuristics against known optima and lower bounds.
[^erickson-struct]: **Erickson**, Ch. 12 — NP-Hardness: exploiting special structure, including fixed-parameter tractability such as $O(2^{k}\cdot n)$ vertex cover.
[^df]: Rodney G. Downey and Michael R. Fellows, _Parameterized Complexity_ (Springer, 1999), and _Fundamentals of Parameterized Complexity_ (2013) — the FPT class, the kernelization/FPT equivalence, and the $\mathsf{W}$-hierarchy with $\mathsf{W}[1]$-hardness of Clique by solution size.