The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following:
A fixed-parameter reduction is a Turing reduction that takes time at most f(k)p(|x|), where f is an arbitrary function and p is a polynomial. Also, if the input is (x,k), then all Weighted 3SAT instances the algorithm queries about must have the form <x',k'> where k' is at most k.
Contains FPT.
Defined in [DF99], where the following is also shown:
W[1] can be generalized to W[t].
Basically has the same relation to W[SAT] as PSPACE does to NP.
The class of decision problems of the form (x,r,k1,...,kr) (r,k1,...,kr parameters), that are fixed-parameter reducible to the following problem, for some constant h:
See W[1] for the definition of fixed-parameter reducibility.
Defined in [DF99].
Contains AW[*], and is contained in AW[P].
The class of optimization problems such that, given an instance of length n, we can find a solution within a factor 1+ε of the optimum in time f(ε)p(n), where p is a polynomial and f is arbitrary.
Contains FPTAS and is contained in PTAS.
Defined in [CT97], where the following was also shown:
The class of decision problems of the form (x,k), k a parameter, that are solvable in time f(k)p(|x|), where f is arbitrary and p is a polynomial.
The basic class of the theory of fixed-parameter tractability, as described by Downey and Fellows [DF99].
To separate FPT and W[2], one could show there is no proof system for CNF formulae that admits proofs of size f(k)nO(1), where f is a computable function and n is the size of the formula.
Contained in FPTnu, W[1], and FPR.
Contains FPTAS [CC97], as well as FPTsu.
Contains EPTAS unless FPT = W[1] [Baz95].
The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:
See W[1] for the definition of fixed-parameter reducibility.
Defined in [DF99].
Contains W[SAT].
The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:
See W[1] for the definition of fixed-parameter reducibility.
Defined in [DF99].
Contains W[t] for every t, and is contained in W[P].
A generalization of W[1].
The class of decision problems of the form (x,k) (k a parameter), that are fixed-parameter reducible to the following problem, for some constant h:
See W[1] for the definition of fixed-parameter reducibility.
Defined in [DF99].
Contained in W[SAT] and in W*[t].