2026-07-23T16:36:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17364 2024-03-06T10:59:33Z ddc:004 open_access

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure Bodlaender, Hans L. Groenland, Carla Jacob, Hugo Jaffke, Lars Lima, Paloma T. parameterized complexity XNLP linear clique-width W-hierarchy pathwidth linear mim-width bandwidth 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Carla Groenland and Hugo Jacob and Lars Jaffke and Paloma T. Lima 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.8 urn:nbn:de:0030-drops-173640 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.8 eng https://creativecommons.org/licenses/by/4.0/legalcode