![]() | ||
Lecture 01
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 in those parameters. This allows the classification of NP-hard problems on a finer scale than in the classical setting, where the complexity of a problem is only measured by the number of bits in the input. The first systematic work on parameterized complexity was done by Downey & Fellows (1999).
Contents
- Lecture 01
- An isomorphism between parameterized complexity and classical complexity for both time and space
- FPT
- W hierarchy
- W1
- W2
- Wt
- WP
- XP
- References
Under the assumption that P ≠ NP, there exist many natural problems that require superpolynomial 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 k. Hence, if k is fixed at a small value and the growth of the function over k is relatively small then such problems can still be considered "tractable" despite their traditional classification as "intractable".
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 (or at least superpolynomial) 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. Such an algorithm is called a fixed-parameter tractable (fpt-)algorithm, because the problem can be solved efficiently for small values of the fixed parameter.
Problems in which some parameter k is fixed are called parameterized problems. A parameterized problem that allows for such an fpt-algorithm is said to be a fixed-parameter tractable problem and belongs to the class FPT, and the early name of the theory of parameterized complexity was fixed-parameter tractability.
Many problems have the following form: given an object x and a nonnegative integer k, does x have some property that depends on k? For instance, for the vertex cover problem, the parameter can be the number of vertices in the cover. 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 interesting to see whether we can find an algorithm which is exponential only in k, 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 languageFor example, there is an algorithm which solves the vertex cover problem in
An isomorphism between parameterized complexity and classical complexity for both time and space
FPT
FPT contains the fixed parameter tractable problems, which are those that can be solved in time
An example is the satisfiability problem, parameterised by the number of variables. A given formula of size m with k variables can be checked by brute force in time
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 k-colouring in time
There are a number of alternative definitions of FPT. For example, the running time requirement can be replaced by
FPT is closed under a parameterised reduction called fpt-reduction, which simultaneously preserves the instance size and the parameter.
Obviously, FPT contains all polynomial-time computable problems. Moreover, it contains all optimisation problems in NP that allow a Fully polynomial-time approximation scheme.
W hierarchy
The W hierarchy is a collection of computational complexity classes. A parameterised problem is in the class W[i], if every instance
Note that
Many natural computational problems occupy the lower levels, W[1] and W[2].
W[1]
Examples of W[1]-complete problems include
W[2]
Examples of W[2]-complete problems include
W[t]
Here, Weighted Weft-t-Depth-d SAT is the following problem:
It can be shown that the problem Weighted t-Normalize SAT is complete for
W[P]
W[P] is the class of problems that can be decided by a nondeterministic
It is known that FPT is contained in W[P], and the inclusion is believed to be strict. However, resolving this issue would imply a solution to the P versus NP problem.
Other connections to unparameterised computational complexity are that FPT equals W[P] if and only if circuit satisfiability can be decided in time
XP
XP is the class of parameterized problems that can be solved in time