18. Complexity: Fixed-Parameter Algorithms

What this lecture covers

The lecture asks what to do with an NP-hard problem when you want an exact answer rather than an approximation, and are willing to accept exponential running time as long as the exponential part is confined to a small "parameter" of the input rather than the whole input size. It follows two earlier lectures, one on proving NP-hardness and one on approximation algorithms, and completes the trio of trade-offs: fast, exact, and works on hard problems — pick two.

Using vertex cover as the running example, you'll see how to design algorithms whose running time is polynomial in the input size and exponential only in a parameter k, and why that matters when k is small in practice. After watching, you should be able to define fixed-parameter tractability (FPT), build a bounded search tree algorithm, apply kernelization to shrink an instance before solving it, and connect FPT to approximation schemes from the previous lecture.

Key ideas

• Parameter: a non-negative integer function of the input, k(x), that measures how hard a particular instance is, such as the target vertex cover size.
• Fixed-parameter tractable (FPT): a problem solvable in time f(k) * poly(n), where the polynomial's exponent does not depend on k.
• Bounded search tree: a recursive algorithm that guesses which endpoint of an uncovered edge belongs in the cover, branching into two smaller subproblems each time k decreases by one.
• Kernelization: a polynomial-time self-reduction that shrinks an instance (x, k) to an equivalent smaller instance (x', k') whose size depends only on k, not on the original input size.
• Multiplicative vs. additive FPT bounds: f(k) * poly(n) and f(k) + poly(n) are provably equivalent definitions, and both are equivalent to having a kernelization procedure.
• High-degree reduction rule: any vertex with degree greater than k must belong to the vertex cover, since leaving it out would force more than k neighbors into the cover.
• EPTAS and FPT: an optimization problem with an efficient polynomial-time approximation scheme (EPTAS) yields an FPT algorithm for the corresponding decision problem, by running the scheme with epsilon just under 1/k.

Walkthrough

Defining parameters and parameterized problems (3:03)

The lecture introduces the general idea of a parameter as a non-negative integer function of the input, giving examples like the number of vertices or edges in a graph. It then defines k-vertex cover: the decision version of vertex cover with an explicit bound k, where k itself is the natural parameter. The goal throughout is a running time polynomial in the overall input size but exponential only in k.

Brute force and why it is "bad" (11:20)

A naive algorithm tries all subsets of k vertices, giving a running time around e * V^k. This is classified as bad because the exponent of n depends on k, so the algorithm is not even polynomial for a fixed k in a useful sense — it becomes impractical quickly as k grows.

Bounded search tree algorithm (18:27)

For any uncovered edge (u, v), at least one endpoint must be in the cover, so the algorithm recursively tries both: add u to the cover, delete it and its edges, decrement k, and recurse; then do the same for v. The recursion tree has height k and branches into two children per node, giving O(V * 2^k) time — exponential only in k, linear in the graph otherwise.

Equivalence of multiplicative and additive FPT, and kernelization theory (28:46)

The lecture proves that f(k) * poly(n) and f(k) + poly(n) describe the same class of problems by splitting into the case n <= f(k) and n >= f(k). It then defines kernelization: a polynomial-time procedure that reduces an instance to an equivalent one whose size depends only on k. The lecture proves an FPT algorithm exists if and only if a kernelization procedure exists, using a similar case split and a "timer" trick when f(k) is not known in advance.

Kernelizing vertex cover (48:14)

A sequence of reduction rules simplifies any vertex cover instance: self-loops force their vertex into the cover, multi-edges collapse to a single edge, and any vertex of degree greater than k must be in the cover. After repeatedly applying these, every remaining vertex has degree at most k, so if a cover of size k exists, the number of edges is at most k^2 and, after deleting isolated vertices, the graph has at most 2k^2 vertices. This produces a quadratic-size kernel in polynomial time; if the kernelized graph is larger than 3k^2, the original instance has no cover of size k.

Combining kernelization with the search algorithms (59:29)

Running brute force on the kernelized graph gives roughly 2^k * k^(2k) time; running the bounded search tree on it gives roughly k^2 * 2^k, a significant improvement, since the exponential part is now singly exponential in k. The lecture notes that further published results push the base below 2, but the kernelization-plus-search-tree combination is the practical takeaway.

Connecting fixed-parameter tractability to approximation schemes (1:04:45)

For an optimization problem with integer optimum, converting to the decision question opt <= k and parameterizing by k links back to the previous lecture's approximation schemes. The lecture proves that if a problem has an efficient PTAS (EPTAS), running it with epsilon slightly below 1/k yields an exact FPT algorithm, because the resulting absolute error is provably less than 1 for integers, forcing the approximate value to equal the optimum. This result is most often used in the contrapositive: showing a problem is not FPT implies it has no EPTAS.

Before you watch

• Know the definition of vertex cover and how it was proven NP-hard, and be comfortable with the greedy 2-approximation algorithm from the previous lecture.
• Review the previous lecture's approximation scheme material (PTAS/FPTAS), since the last section builds directly on it.
• Be comfortable with recursion trees and basic asymptotic analysis, since running times are derived by counting nodes in a branching recursion.

Check your understanding

1. Why does an O(e * V^k) running time count as "bad" for fixed-parameter tractability, even though it is polynomial for any single fixed value of k?
2. Walk through why any vertex with degree greater than k must belong to an optimal vertex cover of size at most k.
3. Explain why proving f(k) * poly(n) running time is equivalent to f(k) + poly(n) running time only requires comparing n to f(k).
4. What does it mean for a kernelization procedure to produce an instance whose size depends only on k, and why does that make any exact algorithm afterward run in FPT time?
5. Why does setting epsilon just below 1/k in an EPTAS turn an approximate solution into an exact one when the optimum is known to be an integer?