Parameterized complexity: Difference between revisions

Revision as of 09:58, 7 September 2022

Revision as of 00:17, 21 December 2022

Line 34:

=== ''W'' hierarchy ===

The '''''W'' hierarchy''' is a collection of computational complexity classes. A parameterized problem is in the class ''W''[''i''], if every instance <math>(x, k)</math> can be transformed (in fpt-time) to a combinatorial circuit that has [[weft (circuit)|weft]] at most ''i'', such that <math>(x, k)\in L</math> if and only if there is a satisfying assignment to the inputs that assigns ''1'' to exactly ''k'' inputs. The weft is the largest number of logical units with unbounded fan-in greater than two on any path from an input to the output. The total number of logical units on the paths (known as depth) must be limited by a constant that holds for all instances of the problem.

Note that <math>\mathsf{FPT} = W[0]</math> and <math>W[i] \subseteq W[j]</math> for all <math>i\le j</math>. The classes in the ''W'' hierarchy are also closed under fpt-reduction.