XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure
Publication date
2022-12-01
Authors
Bodlaender, H.L.
Groenland, Carla
Jacob, Hugo
Jaffke, Lars
Lima, Paloma T.
Editors
Dell, Holger
Nederlof, Jesper
Advisors
Supervisors
Document Type
Part of book
Metadata
Show full item recordCollections
License
cc_by
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.
Keywords
bandwidth, linear clique-width, linear mim-width, parameterized complexity, pathwidth, W-hierarchy, XNLP, Software
Citation
Bodlaender, H L, Groenland, C, Jacob, H, Jaffke, L & Lima, P T 2022, XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure. in H Dell & J Nederlof (eds), 17th International Symposium on Parameterized and Exact Computation, IPEC 2022., 8, Leibniz International Proceedings in Informatics, LIPIcs, vol. 249, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 8:1-8:18, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, Potsdam, Germany, 7/09/22. https://doi.org/10.4230/LIPIcs.IPEC.2022.8, conference