In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input or output. The complexity of a problem is then measured as a function of those parameters. Then the theory analyses how the running time (or space) for solutions to the problem behave as the parameters get larger. To illustrate the idea, the for a fixed k we can solve instances of vertex cover problem (vertices cover edges) in linear time, whereas the only known algorithms for dominating set problem (vertices cover vertices) is more or less search all possible size k subsets and hence require about Ω(n^k) time. When this idea is made formal, the first behaviour is called fixed parameter tractability, since, although both are polynomial time algorithms, the former is of the form O(n^c) independent of the parameter, and the latter is of the form Ω(n^{f(k)).
Researchers had often studied restrictions of problems by restricting parameters such as maximum vertex degree, cutwidth, treewidth, or genus. Several authors had noted that there might be a general method of attacking intractability obtained through understanding the complexity as a function of parameters, including Vardi (in the context of databases) and Regan (in finite model theory). Gurevich, Stockmeyer & Vishkin explicitly noted this: ``The message there is that although it is convenient in theory to express the size of a problem instance as a single number, the size of an instance is sometimes more accurately expressed in termsof several independent parameters, and it may be useful to know the running time of an algorithm as a function of more than one parameter.''
None of these approaches identified the key idea which is classifying problems according to how the exponent of the running time is affected as the parameters increased. The main idea in parameterized complexity is to stratify a problem by (collections of) parameters and then and to classify in terms of how running times grow with the parameter, typically f(k)n^c vs n^{f(k)}.
This idea was first proposed by Abrahamson, Fellows, Ellis and Mata by classifying families of relations. In a series of papers, Downey and FellowsR. Downey, M. Fellows, Fixed-parameter tractability and completeness. Congr. Numer. 87, 161–178 (1992)R. Downey, M. Fellows, Fixed-parameter tractability and completeness. III. Some structural aspects of the W hierarchy, in Complexity Theory: Current Research, Dagstuhl Work-
shop, February 2–8, 1992, ed. by K. Ambos-Spies, S. Homer, U. Schöning (Cambridge
University Press, Cambridge, 1993), pp. 191–225 , sometimes with co-authors, laid the foundations of this area. For a computational complexity theory, we need a notion of what it means to be tractable, methods of comparing problems (reductions), and classes we regard as intractable, along with evidence for this belief. These were first identified in these basic papers.
Although the theory of fixed parameter tractability is most often applied to analyse NP-complete and NP-hard languages, it also can be applied more generally. For example, the definition of fixed-parameter tractability can be applied to (unparameterized) languages of arbitrary complexity, meaning that there are languages L which are not, for example, elementary recursive yet have parameterizations which are fixed parameter tractable. Similarly, problems like Graph Isomorphism which are likely not NP-hard admit tractable parameterizations by fixing maximum degree of a vertex or treewidth.
The existence of efficient, exact, and deterministic solving algorithms for NP-complete, or otherwise NP-hard, problems is considered unlikely, if input parameters are not fixed; all known solving algorithms for these problems require time that is exponential (so in particular super-polynomial) in the total size of the input. However, some problems can be solved by algorithms that are exponential only in the size of a fixed parameter while polynomial in the size of the input.
Under the assumption that P ≠ NP, there exist many natural problems that require super-polynomial running time when complexity is measured in terms of the input size only but that are computable in a time that is polynomial in the input size and exponential or worse in a parameter . Hence, if is fixed at a small value and the growth of the function over is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable".
Such an algorithm is called a fixed-parameter tractable (FPT) algorithm, because the problem can be solved efficiently (i.e., in polynomial time and where the exponent of the polynomial does not increase with the increase of the parameters) for constant values of the fixed parameter. A parameterized problem that allows for such an FPT algorithm is said to be a fixed-parameter tractable problem and belongs to the class , and the early name of the theory of parameterized complexity was fixed-parameter tractability.
The parameterised complexity approach has led to the discover of a large number of new exact algorithmic techniques for problems. These include the method of bounded search trees, color-coding, Courcelle's Theorem, Kernelization, iterative compression, and many others.
Setup Many problems have the following form: given an object and a nonnegative integer , does have some property that depends on ? Other problems are similarly of the form given an object x and another one y can y be found within x where that property depends only on y. For example, if x and y are graphs, is y a minor of x?
For instance, for the vertex cover problem, the parameter can be the number of vertices in the cover. The minimal vertex cover problem asks:
In many applications, for example when modelling error correction, one can assume the parameter to be "small" compared to the total input size. Then it is challenging to find an algorithm that is exponential only in , and not in the input size.
In this way, parameterized complexity can be seen as two-dimensional complexity theory. This concept is formalized as follows:
A parameterized problem is a language , where is a finite alphabet. The second component is called the parameter of the problem. Note that the parameter might itself be a structure rather than a number. Also k might code several parameters at once.
A parameterized problem is fixed-parameter tractable if the question "?" can be decided in running time , where is an arbitrary function depending only on . The corresponding complexity class is called FPT.
A parameterized problem uses the natural parameter when its parameter is the size of the solution to the problem.
For example, there is an algorithm that solves the vertex cover problem in time, where is the number of vertices and is the size of the vertex cover. This means that vertex cover is fixed-parameter tractable with the size of the solution as the parameter (its natural parameter). It is also possible to show vertex cover is in the parameterised version of Logspace, called logspace plus advice, parameterised problems solvable in space .
Complexity classes
FPT FPT (fixed parameter tractable) is the class of decision problems decidable in deterministic time , where is a computable function. Typically, this function is thought of as single exponential, such as , but the definition admits functions that grow even faster. This is essential for a large part of the early history of this class. The crucial part of the definition is to exclude functions of the form , such as n^k or worse.
Strictly speaking this definition is what is called strongly uniform FPT. More general definitions allow for languages L where membership of (x,k) in L is decided by a machine M but f no longer has to be computable and this is called uniformly FPT, and finally L is called nonuniformly FPT if there is a series of algorithms M_k which decide membership in time . For most practical purposes, we can take as being computable, but examples of uniform and nonuniform FPT problems have arisen from the Graph Minor Theorem.
The class FPL (fixed parameter linear) (or LFPT) is the class of problems solvable in time for some computable function . FPL is thus a subclass of FPT. An example is the Boolean satisfiability problem, parameterised by the number of variables. A given formula of size with variables can be checked by brute force in time . A vertex cover of size in a graph of order can be found in time , so the vertex cover problem is also in FPL. Recent developments have identified the class TLFPT (true linear FPT) of problems solvable in time to be important. TLFPT does not equal LFPT by diagonalization. The model for both LFPT and TLFPT is the Word RAM model.
An example of a problem that is thought not to be in FPT is graph coloring parameterised by the number of colors. It is known that 3-coloring is NP-hard, and an algorithm for graph -coloring in time for would run in polynomial time in the size of the input. Thus, if graph coloring parameterised by the number of colors were in FPT, then P = NP.
There are a number of alternative definitions of FPT. For example, the running-time requirement can be replaced by . Also, a parameterised problem is in FPT if it has a so-called kernel. Kernelization is a preprocessing technique that reduces the original instance to its "hard kernel", a possibly much smaller instance that is equivalent to the original instance but has a size that is bounded by a function in the parameter.
FPT is closed under a parameterised notion of reductions called fpt-reductions. We say that one parameterized problem fpt-reduces to iff there exists two functions , such that
iff is itself fixed parameter tractable. That is, there exists a constant , and a function , such that is computable in time
Obviously, FPT contains all polynomial-time computable problems. Moreover, it contains all optimisation problems in NP that allow an efficient polynomial-time approximation scheme (EPTAS). Here is the parameter, and showing a PTAS is hard according to one of the hierarchies below (e.g. W-hard) and this parameter implies that the problem. likely has no EPTAS, and hence no fully polynomial time approximatin scheme.
XP XP is the class of parameterized problems that can be solved in time for some computable function .
These problems are called slicewise polynomial, in the sense that each "slice" of fixed k has a polynomial-time algorithm, although with a possibly different exponent for each k. Compare this with FPT, which merely allows a different constant prefactor for each value of k.
XP strictly contains FPT by diagonalization. There are some natural problems which are complete for XP such as determining winning strategies for the Pebble Game Problem for each parameter k.
para-NP is the class of decision problems decidable in nondeterministic time for some computable function .
if and only if .
A problem is para-NP-hard if it is -hard already for a constant value of the parameter. That is, there is a "slice" of fixed that is -hard. A parameterized problem that is -hard cannot belong to the class , unless . A classic example of a -hard parameterized problem is graph coloring, parameterized by the number of colors, which is already -hard for (see ).
Hierarchies In the parameterized complexity theory, there are some hierarchies of complexity classes. Each such class is closed under fpt-reduction. The most important ones are the W hierarchy and the A hierarchy.
Preliminary definitions