Class Description

W[t]: Nondeterministic Fixed-Parameter Hierarchy

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].

Linked From

#W[t]: Sharp-W[t]

Roughly, the analogue of #P for parameterized complexity. I.e. the class of parameterized counting problems that are fixed-parameter parsimonious reducible to #WSAT.Defined in [FG02], which should be consulted for the full definition. [FG02] also showed that there exist #W[1]-complete problems whose corresponding decision problems are fixed-parameter tractable (i.e. in FPT).

Complete problems for #W[1] include counting the paths or cycles of a given length in a graph and counting the chordless paths of a given length (the latter both under parsimonious and Turing reductions). Complete problems for #W[2] include the maximal chordless path problem. [CF07]

More about...


AW[t]: Alternating W[t]

Has the same relation to W[t] as PSPACE does to NP.

Same as AW[SAT], except that the formula F can have depth at most t.

Defined in [DF99].

Contained in AW[*].

[DFT98] show that for all t, AW[t] = AW[*].

More about...


W[1]: Weighted Analogue of NP

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].

More about...


W[SAT]: Weighted Satisfiability

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].

More about...


W[*]: Union of W[t]'s

The union of W[t] over all t.

More about...


W*[t]: W[t] With Parameter-Dependent Depth

Same as W[t], except that now the circuit depth can depend on the parameter k rather than being constant. (The number of unbounded-fanin gates along any path to the root is still at most t.)

W*[1] = W[1] [DFT96], and W*[2] = W[2] [DF97], but the problem is open for larger t.

More about...