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 (ACM Trans Comput Theory 9:1–36, 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, Capacitated Vertex Cover and Bipartite Bandwidth.
| Original language | English |
|---|---|
| Pages (from-to) | 465-506 |
| Journal | Algorithmica |
| Volume | 87 |
| Early online date | 4 Nov 2024 |
| DOIs | |
| Publication status | Published - Apr 2025 |
Bibliographical note
Publisher Copyright:© The Author(s) 2024.
Funding
Carla Groenland was supported by the European Union's Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Sk & lstrok;odowska-Curie grant GRAPHCOSY (number 101063180). Lars Jaffke was supported by the Norwegian Research Council (project number 274526) and the Meltzer Research Fund. The authors have no further relevant financial or non-financial interests to disclose.
| Funders | Funder number |
|---|---|
| Norwegian School of Economics | 853234, 101063180 |
| European Union's Horizon 2020 research and innovation programme under the ERC | 274526 |
| Norwegian Research Council | |
| Meltzer Research Fund |
Keywords
- Bandwidth
- Linear clique-width
- Linear mim-width
- Parameterized complexity
- Pathwidth
- XNLP