Parameterized complexity: Difference between revisions

Revision as of 07:25, 23 April 2020

Revision as of 01:52, 27 June 2020

Line 16:

:A parameterized problem {{mvar|L}} 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 {{mvar|f}} is an arbitrary function depending only on {{mvar|k}}. 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, <ref>{{harvnb|Chen|Kanj|Xia|2006}}</ref> where {{mvar|n}} is the number of vertices and {{mvar|k}} is the size of the vertex cover. This means that vertex cover is fixed-parameter tractable with the size of the solution as the parameter.

== Complexity classes ==

Line 81:

=== para-NP ===

'''para-NP''' is the class of parameterized problems that can be solved by a [[Nondeterministic algorithm|nondeterministic algorithm]] in time <math>f(k) \cdot |x|^{O(1)}</math> for some computable function <math>f</math>. It is known that <math>\text{FPT}=\text{para-NP}</math> if and only if <math>\text{P}=\text{NP}</math>. {{sfnp|Flum|Grohe|page=39}}

A problem is '''para-NP-hard''' if it is <math>\text{NP}</math>-hard already for a constant value of the parameter. That is, there is a "slice" of fixed <math>k</math> that is <math>\text{NP}</math>-hard. A parameterized problem that is <math>\text{para-NP}</math>-hard cannot belong to the class <math>\text{XP}</math>, unless <math>\text{P}=\text{NP}</math>. A classic example of a <math>\text{para-NP}</math>-hard parameterized problem is [[Graph coloring|graph coloring]], parameterized by the number <math>k</math> of colors, which is already <math>\text{NP}</math>-hard for <math>k=3</math> (see [[Graph coloring#Computational_complexityComputational complexity]]).

=== A hierarchy ===

Line 200:

* [http://www.sprg.uniroma2.it/home/cesati/research/compendium/ Compendium of Parameterized Problems]

[[Category:Computational complexity theory]]

[[Category:Parameterized complexity| ]]

[[Category:Computational complexity theory]]