Content deleted Content added
m Fix links to disambiguation page Function |
→FPT: “... if graph coloring parameterised by the number of colors were in FPT,...” is more accurate than “... if graph coloring were in FPT,...” |
||
Line 31:
An example is the [[satisfiability]] problem, parameterised by the number of variables. A given formula of size ''m'' with ''k'' variables can be checked by brute force in time <math>O(2^km)</math>. A [[vertex cover]] of size ''k'' in a graph of size ''m'' can be found in time <math>O(2^km)</math>, so this problem is also in FPT.
An example of a problem that is not supposed to be in FPT is [[graph coloring]] parameterised by the number of colors. It is known that 3-coloring is [[NP-hard]], and an algorithm for graph ''k''-colouring in time <math>f(k)n^{O(1)}</math> for ''k''=3 would run in polynomial time in the size of the input. Thus, if graph
There are a number of alternative definitions of FPT. In particular, the running time requirement can be replaced by <math>f(k) + |x|^{O(1)}</math>. Also, a parameterised problem is in FPT if it has a so-called kernel. Kernelisation is a precomputation technique reducing the original instance to its “hard kernel”, a much smaller instance that is in some sense computationally equivalent to the original instance but of size polynomial in the parameter.
| |||