Parameterized complexity: Difference between revisions

Revision as of 20:36, 16 May 2009

Revision as of 11:31, 17 December 2009

Line 13:

:A ''parameterized problem'' is a language <math>L \subseteq \Sigma^* \times \N</math>, where <math>\Sigma</math> is a finite alphabet. The second component is called the ''parameter'' of the problem.

:A parameterized problem <math>L</math> is ''fixed-parameter tractable'' if the question &ldquo;<math>(x, k) \in L</math>?&rdquo; can be decided in running time <math>f(k) \cdot |x|^{O(1)})</math>, where <math>f</math> is an arbitrary function depending only on <math>k</math>. The corresponding complexity class is called '''FPT'''.

For example, there is an algorithm which solves the vertex cover problem in <math>O(kn + 1.274^k)</math> time, where <math>n</math> is the number of vertices and <math>k</math> is the size of the vertex cover. This proves that vertex cover is fixed-
parameter tractable with respect to this parameter.

==W hierarchy==

The W hierarchy is a collection of computational complexity classes used in the theory of parameterised complexity, classifying computational problems according to their apparent intractability in terms of another parameter than input size. The largest class, W[P], can be understood as an attempt to define a parameterised analogue of [[NP]]. At the bottom of the hierarchy, the class FPT contains the fixed-parameter tractable problems, which are easy from the point of view of parameterised computation. Many natural computational problems occupy the lower levels, W[1] and W[2].

The classes in the W hierarchy are closed under a parameterised reduction called fpt-reduction, which simultaneously preserves the instance size and the parameter. This reduction allows the definition of problems that are complete (under fpt-reduction) for the classes of the W-hierarchy.

===FPT===

FPT contains the ''fixed parameter tractable'' problems, which are those that can be solved in time <math>O(f(k)|x|^{O(1)})</math> for some computable function ''f''. Typically, this function is thought of as single exponential, such as <math>2^{O(k)}</math> 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 <math>f(n,k)</math>, such as <math>n^k</math>.

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 <math>O(2^km)</math>. A [[vertex cover]] of size ''k'' in a graph of size ''m'' can be found in time <math>O(2^km)</math>, so this problem is also in FPT.

An example of a problem that is not supposed 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 <math>O(f(k)n^{O(1)})</math> for ''k''=3 would run in polynomial time in the size of the input. Thus, if graph colouring were in FPT, then P=NP.

There are a number of alternative definitions of FPT. In particular, the running time requirement can be replaced by <math>O(f(k) + |x|^{O(1)})</math>. Also, a parameterised problem is in FPT if it has a so-called kernel. Kernelisation is a precomputation technique reducing the original instance to its “hard kernel”, a much smaller instance that is in some sense computationally equivalent to the original instance but of size polynomial in 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[1]===

W[1] includes the first class of problems not believed to be in FPT.

An example is deciding if an ''n''-vertex graph contains an [[independent set]] of cardinality ''k''. This question can be decided in time <math>O(n^kn^2)</math> by inspecting all vertex subsets of size ''k''; this running time is not fixed-parameter tractable, and no algorithm with a running time of the form <math>O(f(k)n^{O(1)})</math> is known.

===W[2]===

A complete problem for W[2] is deciding if a given graph contains a [[dominating set]] of size ''k''.

===W[P]===

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 $\exp(o(n))m^{O(1)}$, or if and only if there is a computable, nondecreasing, unbounded function f such that all languages recognised by a nondeterministic polynomial-time Turing machine using f(n)log n nondeterministic steps are in P.

==References==