A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy

Abstract

We present a list of parameterized problems together with a complexity classification of whether they allow a fixed-parameter tractable reduction to SAT or not. These problems are parameterized versions of problems whose complexity lies at the second level of the Polynomial Hierarchy or higher.

Keywords

• parameterized complexity
• polynomial hierarchy
• fpt-reductions