A Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy
| Authors |
|
|---|---|
| Publication date | 09-2019 |
| Journal | Algorithms |
| Article number | 188 |
| Volume | Issue number | 12 | 9 |
| Number of pages | 28 |
| Organisations |
|
| 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. |
| Document type | Article |
| Language | English |
| Published at | https://doi.org/10.3390/a12090188 |
| Downloads |
algorithms-12-00188-v2
(Final published version)
|
| Permalink to this page | |