Parameterized complexity: Difference between revisions

Revision as of 15:46, 14 April 2006

Revision as of 16:00, 14 April 2006

Line 1:

In [[computer science]], '''parameterized complexity''' is a measure of complexity of problems with multiple inputs. It is based on the fact that several such [[NP-hard]] are [[tractable]] when one of their input is fixed.

In [[computer science]], '''fixed-parameter algorithms''' are an approach to attacking [[NP-hard]] problems with multiple inputs. It is believed to be difficult to find efficient, exact, deterministic solutions to these problems; all known solutions require time that is [[Exponential time|exponential]] in the total size of the inputs. However, it may be possible to find an algorithm which is exponential in the size of only one input and polynomial in the size of the other inputs. Such an algorithm is called a fixed-parameter algorithm, because if we fix the single troublesome input at any one value, the problem can be solved efficiently.

The existence of efficient, exact, and deterministic solving algorithms for [[NP-complete]] problems problems is considered unlikely, if inputs are not fixed; all known solving algorithma for these problems require time that is [[Exponential time|exponential]] in the total size of the inputs. However, some problems can be solved by algorithms that are exponential in the size of one input and polynomial in the size of the other inputs. Such an algorithm is called a '''fixed-parameter algorithm''', because the problem can be solved efficiently by fixing the "troublesome" input at any one value. <!-- is this correct? it somehow implies that FPT=constant input --> A problem that allows for such an algorithm is called '''fixed-parameter tractable''', and the early name of the theory of parameterized complexity was '''fixed-parameter tractability'''.

In particular, many problems have the following general form: given an object <math>x</math> and a nonnegative integer <math>k</math>, does <math>x</math> have some property that depends on <math>k</math>? 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 <math>k</math>, and not in the input size.

In particular, manyMany problems have the following general form: given an object <math>x</math> and a nonnegative integer <math>k</math>, does <math>x</math> have some property that depends on <math>k</math>? 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 <math>k</math>, 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:

Line 9 ⟶ 11:

: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.29^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.

==References==