Abstract
In this paper, we showcase the class XNLP as a natural place for many hard problems parameterized by linear width measures. This strengthens existing W[1]-hardness proofs for these problems, since XNLP-hardness implies W[t]-hardness for all t. It also indicates, via a conjecture by Pilipczuk and Wrochna [ToCT 2018], that any XP algorithm for such problems is likely to require XP space. In particular, we show XNLP-completeness for natural problems parameterized by pathwidth, linear clique-width, and linear mim-width. The problems we consider are Independent Set, Dominating Set, Odd Cycle Transversal, (q-)Coloring, Max Cut, Maximum Regular Induced Subgraph, Feedback Vertex Set, Capacitated (Red-Blue) Dominating Set, and Bipartite Bandwidth.
| Original language | English |
|---|---|
| Title of host publication | 17th International Symposium on Parameterized and Exact Computation, IPEC 2022 |
| Editors | Holger Dell, Jesper Nederlof |
| Publisher | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
| Pages | 8:1-8:18 |
| Number of pages | 18 |
| ISBN (Electronic) | 9783959772600 |
| ISBN (Print) | 9783959772600 |
| DOIs | |
| Publication status | Published - 1 Dec 2022 |
| Event | 17th International Symposium on Parameterized and Exact Computation, IPEC 2022 - Potsdam, Germany Duration: 7 Sept 2022 → 9 Sept 2022 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 249 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 17th International Symposium on Parameterized and Exact Computation, IPEC 2022 |
|---|---|
| Country/Territory | Germany |
| City | Potsdam |
| Period | 7/09/22 → 9/09/22 |
Bibliographical note
Funding Information:Funding Carla Groenland: Supported by the European Union’s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Skłodowska-Curie grant GRAPHCOSY (number 101063180). Lars Jaffke: Supported by the Norwegian Research Council (project number 274526) and the Meltzer Research Fund.
Publisher Copyright:
© Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Lars Jaffke, and Paloma T. Lima.
Funding
Funding Carla Groenland: Supported by the European Union’s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Skłodowska-Curie grant GRAPHCOSY (number 101063180). Lars Jaffke: Supported by the Norwegian Research Council (project number 274526) and the Meltzer Research Fund.
Keywords
- bandwidth
- linear clique-width
- linear mim-width
- parameterized complexity
- pathwidth
- W-hierarchy
- XNLP