Parameterized complexity

Parameterized complexity classifies computational problems by how their running time depends on input size and a chosen parameter, distinguishing fixed-parameter tractability from parameter-dependent exponentials.

Fixed-parameter tractability: A problem is fixed-parameter tractable if it can be solved in time f(k)n^c for parameter k, computable f, and constant c. This is the central tractability standard: the parameter affects a multiplicative factor, not the input-size exponent.
Parameterized problem: A parameterized problem is a decision or computational problem whose instances carry an integer parameter alongside the input. The separate parameter is the basic object that the theory classifies.
Branch and bound: Branch and bound searches a solution space by splitting cases and pruning branches using bounds. Parameterized analyses explain when branching can yield fixed-parameter running times.
Rod Downey: Rod Downey is a mathematician whose work helped establish parameterized complexity as a distinct theory of computational complexity. His foundational research developed key parameterized classes and completeness results.
Parameterized reduction: A parameterized reduction transforms one parameterized problem into another while controlling output size, parameter growth, and computation time. These reductions compare problem difficulty while preserving the parameterized setting.
Clique problem: The clique problem asks whether a graph contains a complete subgraph of at least a specified size. With clique size as parameter, it is a canonical W[1]-complete problem.
Color coding: Color coding is a randomized technique that detects small structures by assigning colors and searching for colorful solutions. It gives fixed-parameter algorithms for patterns such as paths and trees.
Michael Fellows: Michael Fellows is a computer scientist known for foundational work in parameterized complexity and its structural theory. His collaborations helped define the field’s early framework.
Kernelization: A kernelization is a polynomial-time reduction to an equivalent instance whose size is bounded by a function of the parameter. A small kernel captures fixed-parameter tractability through preprocessing.
Vertex cover: A vertex cover is a set of graph vertices incident to every edge; finding one of bounded size is a standard parameterized problem. Its size parameter supports classic fixed-parameter algorithms and kernelization.

Linked from 12 pages