A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
Ronald de Haan, Stefan Szeider · Algorithms · 2019
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.