Machine-based methods in parameterized complexity theory

We give machine characterizations of most parameterized complexity classes, in particular, of W[P], of the classes of the W-hierarchy, and of the A-hierarchy. For example, we characterize W[P] as the class of all parameterized problems decidable by a nondeterministic fixed-parameter tractable algorithm whose number of nondeterministic steps is bounded in terms of the parameter. The machine characterizations suggest the introduction of a hierarchy W func between the W- and the A-hierarchy. We study the basic properties of this hierarchy.

Authors

• Yijia Chen
• Jörg Flum
• Martin Grohe

Keywords

• Parameterized complexity
• Machine characterizations
• Complexity classes