Content deleted Content added
W hierarchy |
m →W hierarchy: change square brackets to open ones for wikisyntax (is this really a good idea?) |
||
Line 36:
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
W(1), commonly written as '''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
A complete problem for W[2] is deciding if a given graph contains a [[dominating set]] of size ''k''.
===W
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.
| |||