Fixed-parameter tractability

Fixed-parameter tractability is an algorithmic framework in which a problem is solved in time f(k)n^c, with arbitrary computable f, input size n, parameter k, and constant c.

Parameterized algorithm: An algorithm analyzed in terms of input size and a separate parameter that captures problem structure. Fixed-parameter tractability is the central efficiency guarantee sought in this broader algorithmic framework.
Parameterized complexity: The study of computational problems classified by how their difficulty depends on input size and a parameter. Fixed-parameter tractability is its foundational tractability class.
Vertex Cover: The problem of finding the smallest set of graph vertices that touches every edge. A solution of size k can be found in time exponential in k and polynomial in graph size.
XP (complexity): The class of parameterized problems solvable in time n^{f(k)} for some computable function f. XP permits the exponent of input size to grow with the parameter, unlike fixed-parameter tractability.
Parameterized algorithm design: The practice of designing algorithms whose complexity is analyzed using a parameter beyond input length. Fixed-parameter tractability motivates methods that isolate and exploit small structural features.
Kernelization: A polynomial-time reduction that compresses an instance to an equivalent instance whose size is bounded by its parameter. Kernelization offers a complementary route to tractability by shrinking inputs before expensive computation.
Parameter (computational complexity): A numerical measure of an instance's structure or requested solution size, treated separately from total input length. The choice of parameter determines which part of an algorithm's cost may grow exponentially.
Feedback Vertex Set: The problem of deleting the fewest vertices from a graph to leave no cycles. Its parameterized algorithms exploit the requested deletion-set size as the parameter.
FPT approximation: An approximation algorithm whose running time is fixed-parameter tractable and whose guarantee is controlled by an accuracy parameter. It extends parameterized efficiency to settings where exact optimization is too costly.
Parameterized complexity dichotomy: A classification dividing problem families into fixed-parameter tractable and parameterized-intractable cases. Dichotomy results identify which structural settings support efficient parameterized algorithms.

Linked from 6 pages