TY - GEN
T1 - XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
AU - Bodlaender, Hans L.
AU - Groenland, Carla
AU - Jacob, Hugo
AU - Jaffke, Lars
AU - Lima, Paloma T.
N1 - 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.
PY - 2022/12/1
Y1 - 2022/12/1
N2 - 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.
AB - 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.
KW - bandwidth
KW - linear clique-width
KW - linear mim-width
KW - parameterized complexity
KW - pathwidth
KW - W-hierarchy
KW - XNLP
UR - http://www.scopus.com/inward/record.url?scp=85144220234&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.IPEC.2022.8
DO - 10.4230/LIPIcs.IPEC.2022.8
M3 - Conference contribution
AN - SCOPUS:85144220234
SN - 9783959772600
T3 - Leibniz International Proceedings in Informatics, LIPIcs
SP - 8:1-8:18
BT - 17th International Symposium on Parameterized and Exact Computation, IPEC 2022
A2 - Dell, Holger
A2 - Nederlof, Jesper
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 17th International Symposium on Parameterized and Exact Computation, IPEC 2022
Y2 - 7 September 2022 through 9 September 2022
ER -