Parameterized Algorithms

Most computer science students learn early that some problems are NP-hard: no known efficient algorithm solves them exactly on all inputs, and if one existed, it would settle the famous P versus NP question.

13 frameworks, from 1988 to today · Algorithms · Computer Science

still a working view ended · each leads to its entry below

Overview

Most computer science students learn early that some problems are NP-hard: no known efficient algorithm solves them exactly on all inputs, and if one existed, it would settle the famous P versus NP question. That verdict, though, is a statement about worst cases over all inputs. It says nothing about the inputs that actually arrive in practice, which often carry hidden structure—a network that is almost a tree, a scheduling instance with only a handful of machines, a verification task where the answer is small. Parameterized algorithms is the branch of algorithmics that asks: when a hard problem comes with a small structural quantity attached, can we confine the combinatorial explosion to that quantity and keep everything else polynomial1? The quantity is called the parameter, and the field's central goal is to design algorithms whose running time looks like $f(k)\cdot n^{c}$—exponential or worse in the parameter $k$, but only polynomial in the input size $n$1. When such an algorithm exists, a problem that is intractable in general becomes tractable on the structured instances that matter1.

The 1980s: Fixed-Parameter Tractability and the First Techniques

The intellectual roots reach back to the 1980s, when researchers in computational logic and graph theory noticed that certain NP-hard problems become easy once a bound is placed on some structural feature. A landmark was the 1988 paper by Rod Downey and Michael Fellows, "Fixed-Parameter Tractability and Completeness I," which gave the notion a name and a theory. A problem is fixed-parameter tractable (FPT) with respect to a parameter $k$ if it can be solved in time $f(k)\cdot n^{c}$ for some computable function $f$ and constant $c$1. The definition matters because it separates two kinds of exponential cost: growth in the parameter, which may be unavoidable, and growth in the input, which is not.

The earliest FPT algorithms were built by bounded search tree methods. The idea is to branch on a small local structure and recurse, with the branching depth bounded by the parameter. The classic example is Vertex Cover: given a graph and an integer $k$, is there a set of at most $k$ vertices touching every edge1? Pick any uncovered edge; any solution must contain one of its two endpoints, so branch on both, decrease $k$ by one, and recurse. The search tree has at most $2^{k}$ leaves, giving an $O(2^{k}\cdot n)$ algorithm. The same style handles many problems where a small "witness" can be found by systematic guessing. These algorithms are simple and often practical, and they established the template: find a bounded branching rule, and the parameter pays for the tree.

The 1990s: A Complexity Theory of Parameters

A technique without a hardness theory is only half a science. Downey and Fellows supplied the other half by building a hierarchy of parameterized complexity classes, the W-hierarchy: FPT sits at the bottom, and above it lie W[1], W[2], and so on. The classes are defined through reductions that preserve the parameter, and they let researchers say of a problem not merely "no FPT algorithm is known" but "it is W[1]-hard, so an FPT algorithm would imply a collapse of the hierarchy," in the same spirit as NP-hardness. The canonical W[1]-complete problem is Clique parameterized by the size of the clique; Independent Set and Dominating Set are standard W[2]-hard examples. This framework, consolidated in Downey and Fellows' 1999 monograph Parameterized Complexity, gave the field its vocabulary and its standards of evidence.

Alongside the theory came a sharper toolkit. Kernelization is the art of preprocessing: reduce an instance in polynomial time to an equivalent instance—the kernel—whose size is bounded by a function of $k$ alone12. A kernel of size $g(k)$ yields an FPT algorithm by brute force on the kernel, and conversely every FPT problem has a kernel (possibly enormous)12. The Vertex Cover problem again served as the showcase: a classical reduction rule—if a vertex has more than $k$ neighbors, it must be in every solution of size at most $k$—repeatedly shrinks the graph until it has at most $2k$ vertices. Kernelization turned preprocessing from folklore into a theory with lower bounds of its own, asking how small a kernel a problem can possibly have.

Color coding, introduced by Noga Alon, Raphael Yuster, and Uri Zwick in 1995, attacked the problem of finding small subgraphs—paths, cycles, trees—of a specified size $k$. Randomly color the vertices with $k$ colors; a desired subgraph is colorful (all colors distinct) with probability about $e^{-k}$, and a colorful copy can be found by dynamic programming over color subsets in time $2^{k}\cdot n^{c}$. Repeating the coloring a few times and derandomizing with perfect hash families gives a randomized or deterministic FPT algorithm. It was an early demonstration that randomization and algebraic ideas could beat naive branching.

The 2000s: Structure, Width, and the Graph Minors Engine

The next wave exploited deep structural theorems. Courcelle's theorem, proved by Bruno Courcelle in 1990, states that any property expressible in monadic second-order logic can be decided in linear time on graphs of bounded treewidth—a measure of how close a graph is to a tree3. Combined with algorithms that compute tree decompositions, this gave a uniform FPT method for a vast family of problems on bounded-treewidth graphs. The underlying technique, width-parameterized dynamic programming, computes answers bottom-up along a tree decomposition, with a table whose size depends exponentially on the width but polynomially on the graph. It is the structural counterpart to branching: instead of guessing a solution, one exploits the graph's shape.

Treewidth itself became a parameter of central importance, and the graph minors theory of Neil Robertson and Paul Seymour—a monumental series of papers running from the 1980s into the 2000s—supplied the structural facts that made width-based algorithms powerful. A striking consequence is that many problems are FPT when parameterized by the size of a solution because the solution's existence forces bounded structure elsewhere; the theory of bidimensionality, developed by Demaine, Fomin, Hajiaghayi, and Thilikos in the mid-2000s, turned this into a systematic method for obtaining subexponential FPT algorithms on planar and other sparse graph classes.

A parallel development was iterative compression, introduced around 2004 by Reed, Smith, and Vetta for the Odd Cycle Transversal problem and quickly adapted to Feedback Vertex Set and others. The method builds a solution incrementally: maintain a solution of size $k+1$ for a growing subinstance, and when a new element arrives, either the solution already works or a small "compression" step finds a solution of size $k$4. It is a clever way to convert a hypothetical small solution into an algorithm, and it produced some of the fastest known algorithms for feedback-set-type problems.

Important Separators and the Measure-and-Conquer Era

Around the same time, the study of important separators—a notion from the work of Marx and others on multiway cuts—gave a powerful tool for problems where one must separate parts of a graph at bounded cost. The number of important separators of size at most $k$ is bounded by $4^{k}$, which makes enumeration feasible and yields FPT algorithms for problems such as Multicut and Directed Feedback Vertex Set in various parameterizations. This line of work exemplified a broader trend: the 2000s and 2010s saw a proliferation of sophisticated branching measures, where the analysis tracks a potential function that decreases faster than the naive bound suggests, giving running times like $1.27^{k}$ or $1.62^{k}$ instead of $2^{k}$.

Lower Bounds and the Limits of FPT

As the algorithmic side matured, the field turned to proving that some problems are not FPT under standard assumptions. The parameterized complexity hierarchy provided the main vehicle: W[1]-hardness and W[2]-hardness rule out FPT algorithms unless the hierarchy collapses. More recently, conditional lower bounds have sharpened the picture. Under the Exponential Time Hypothesis (ETH)—the conjecture that 3-SAT cannot be solved in subexponential time—researchers can prove that certain problems have no algorithm running in time $2^{o(k)}\cdot n^{c}$, or that a kernel of a certain size cannot exist unless NP is contained in coNP/poly. These results, developed largely from the 2010s onward, give the field a hardness theory comparable in ambition to classical NP-completeness, and they guide algorithm designers toward the best possible exponents.

Approximation and the Present

Not every hard problem yields to exact FPT methods, and a productive compromise is the parameterized approximation algorithm: allow an approximate answer, but demand FPT running time5. For problems like k-Center or Steiner Tree, approximation can circumvent parameterized hardness, and the field has developed a rich theory of when approximation and parameterization combine. Today the main approaches in use descend directly from the history above: bounded search trees and measure-and-conquer branching for solution-size parameters; kernelization as a standard first step and a subject of its own lower-bound theory; width-parameterized dynamic programming and Courcelle-style logic for structural parameters; color coding and algebraic methods for subgraph-finding; iterative compression and important separators for cut and feedback problems; and a mature hardness apparatus of W-hierarchy results and ETH-based conditional lower bounds. Open questions remain about the exact frontiers of kernel sizes, the optimal exponents for many classic problems, and how parameterized ideas interact with approximation and with the fine-grained complexity of polynomial-time solvable problems.

References

  1. Parameterized complexity (introduction, Setup, FPT), Wikipedia
  2. Kernelization, Wikipedia
  3. Courcelle's theorem, Wikipedia
  4. Iterative compression, Wikipedia
  5. Parameterized approximation algorithm, Wikipedia

The frameworks of Parameterized Algorithms

Each framework is a way of working the field has used: when it held, and the question it answers.

  1. 1988-Present

    Bounded Search Tree Branching

    How can we systematically guess a small solution?

    Fly to its tower in Nousfarer

  2. 1988-Present

    Fixed-Parameter Tractability

    When does a hard problem become tractable with a small parameter?

    Fly to its tower in Nousfarer

  3. 1990-Present

    Courcelle's theorem

    When can logical properties be decided efficiently on structured graphs?

    Fly to its tower in Nousfarer

  4. 1990-Present

    Width-Parameterized Dynamic Programming

    How can we exploit tree-like structure to solve problems efficiently?

    Fly to its tower in Nousfarer

  5. 1992-Present

    Parameterized Complexity Hierarchy

    How can we classify problems that are hard to parameterize?

    Fly to its tower in Nousfarer

  6. 1995-Present

    Color Coding

    How can we find small patterns in large graphs efficiently?

    Fly to its tower in Nousfarer

  7. 1997-Present

    Kernelization

    How can we preprocess a problem to a small equivalent instance?

    Fly to its tower in Nousfarer

  8. 2004-Present

    Iterative Compression

    How can we build a solution incrementally while keeping it small?

    Fly to its tower in Nousfarer

  9. 2005-Present

    Bidimensionality

    When do planar problems admit subexponential algorithms?

    Fly to its tower in Nousfarer

  10. 2005-Present

    Measure-and-Conquer Analysis

    How can we analyze branching algorithms more precisely?

    Fly to its tower in Nousfarer

  11. 2005-Present

    Parameterized approximation algorithm

    When can we approximate hard problems efficiently with a parameter?

    Fly to its tower in Nousfarer

  12. 2006-Present

    Important Separators

    How can we separate parts of a graph at small cost?

    Fly to its tower in Nousfarer

  13. 2010-Present

    Conditional Lower Bounds

    What are the limits of efficient parameterized algorithms?

    Fly to its tower in Nousfarer

How the ideas connect

Each arrow runs from an earlier idea to the later one it shaped. The list below says what passed between them.

Bounded Search Tree BranchingFixed-Parameter TractabilityCourcelle's theoremWidth-Parameterized Dynamic Programmi…Parameterized Complexity HierarchyColor CodingKernelizationIterative CompressionBidimensionalityMeasure-and-Conquer AnalysisParameterized approximation algorithmImportant SeparatorsConditional Lower Bounds

Beyond the field

Where Parameterized Algorithms's ideas came from in other fields, and what they led to there: the strongest 12 of 16 links.

A city in Nousfarer: a red-carpeted stair climbing terraces to a crowned tower on an acropolis, more towers round it, forest and snowy mountains beyond.
A city in Nousfarer, the game played in the browser.

Parameterized Algorithms is a planet in Nousfarer

Its city has a tower for each of these 13 frameworks. Land, walk in, and climb one concept at a time.

Land on Parameterized Algorithms

Related fields

Fields its ideas are linked to

More in Algorithms

See where Parameterized Algorithms sits on the Map of Human Knowledge