Parameterized complexity: Difference between revisions

Revision as of 15:45, 26 August 2006

Revision as of 16:01, 26 August 2006

Line 1:

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

The existence of efficient, exact, and deterministic solving algorithms for [[NP-complete]], or otherwise [[NP-hard]], problems is considered unlikely, if inputsinput parameters are not fixed; all known solving algorithms for these problems require time that is [[Exponential time|exponential]] in the total size of the inputsinput. However, some problems can be solved by algorithms that are exponential only in the size of onea inputfixed andparameter while polynomial in the size of the otherinput inputssize. Such an algorithm is called a '''[[fixed-parameter tractable]] (fpt-)algorithm''', because the problem can be solved efficiently byfor fixingsmall thevalues "troublesome"of inputthe at anyfixed one valueparameter. <!--

Problems isin thiswhich correct?some itparameter somehowk impliesis thatfixed FPT=constantare inputcalled -->parameterized problems. A parameterized problem that allows for such an fpt-algorithm is calledsaid to be a '''fixed-parameter tractable''' problem and belongs to the class <math>FPT</math>, and the early name of the theory of parameterized complexity was '''fixed-parameter tractability'''.

Many problems have the following 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.