Treffer: XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure: XNLP-completeness for parameterized problems on graphs with a linear structure

Title:
XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure: XNLP-completeness for parameterized problems on graphs with a linear structure
Authors:
Bodlaender, Hans L., Groenland, Carla, Jacob, Hugo, Jaffke, Lars, Lima, Paloma Thome de
Contributors:
Hans L. Bodlaender and Carla Groenland and Hugo Jacob and Lars Jaffke and Paloma T. Lima, Sub Algorithms and Complexity, Sub Mathematical Modeling, Algorithms and Complexity, Dell, Holger, Nederlof, Jesper
Source:
Leibniz International Proceedings in Informatics
8:1-8:18
Algorithmica
17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
IPEC
Publication Status:
Preprint
Publisher Information:
Springer Science and Business Media LLC, 2024.
Publication Year:
2024
Subject Terms:
bandwidth, FOS: Computer and information sciences, XP space requirement, Parameterized complexity, tractability and kernelization, Pathwidth, Linear clique-width, 0102 computer and information sciences, 02 engineering and technology, Computational Complexity (cs.CC), 01 natural sciences, 7. Clean energy, Bandwidth, Graph algorithms (graph-theoretic aspects), 0202 electrical engineering, electronic engineering, information engineering, Complexity classes (hierarchies, relations among complexity classes, etc.), linear mim-width, parameterized complexity, pathwidth, Parameterized complexity, Computer Science - Computational Complexity, Graph theory (including graph drawing) in computer science, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), XNLP, linear width measures, hardness proofs, ddc:004, W-hierarchy, Linear mim-width, Software, linear clique-width
Document Type:
Fachzeitschrift Article<br />Conference object<br />Part of book or chapter of book
File Description:
application/xml; application/pdf
Language:
English
ISSN:
1432-0541
0178-4617
DOI:
10.1007/s00453-024-01274-9
DOI:
10.48550/arxiv.2201.13119
DOI:
10.4230/lipics.ipec.2022.8
Access URL:
http://arxiv.org/abs/2201.13119
https://research-portal.uu.nl/en/publications/df89aedd-7a2e-4055-938c-d21b56bced16
https://doi.org/10.1007/s00453-024-01274-9
https://hdl.handle.net/11250/3041006
https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.8
https://dspace.library.uu.nl/handle/1874/425595
https://hdl.handle.net/11250/3170553
Rights:
CC BY
arXiv Non-Exclusive Distribution
Accession Number:
edsair.doi.dedup.....193c511eaff4ed15b3e5a7da32dc353b
Database:
OpenAIRE

Weitere Informationen

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.