Parameterized complexity: Difference between revisions

Revision as of 01:06, 15 June 2005

Revision as of 01:06, 15 June 2005

Line 1:

In [[computer science]], '''fixed-parameter algorithms''' are an approach to attacking [[NP-hard]] problems. When trying to solve these problems exactly and deterministically, one has to deal with exponential running times; [[computational complexity theory]] indicates this is [[Complexity classes P and NP|inevitable]]. Parameterized complexity theory accepts these exponential running times, but claims that not all "intractable" algorithms are equal, and some might even be feasible for practical applications.

The main idea is to consider ''parameters''. 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 this way, parameterized complexity can be seen as ''two-dimensional'' complexity theory. This concept is formalized as follows:

Line 9:

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

[[Category:Computational complexity theory]]