dc.contributor.author | Bodlaender, Hans L. | |
dc.contributor.author | Groenland, Carla | |
dc.contributor.author | Jacob, Hugo | |
dc.contributor.author | Jaffke, Lars | |
dc.contributor.author | Lima, Paloma Thome de | |
dc.date.accessioned | 2023-01-04T14:04:04Z | |
dc.date.available | 2023-01-04T14:04:04Z | |
dc.date.created | 2023-01-03T09:54:05Z | |
dc.date.issued | 2022 | |
dc.identifier.issn | 1868-8969 | |
dc.identifier.uri | https://hdl.handle.net/11250/3041006 | |
dc.description.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. | en_US |
dc.language.iso | eng | en_US |
dc.publisher | Dagstuhl Publishing | en_US |
dc.rights | Navngivelse 4.0 Internasjonal | * |
dc.rights.uri | http://creativecommons.org/licenses/by/4.0/deed.no | * |
dc.title | XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure | en_US |
dc.type | Journal article | en_US |
dc.type | Peer reviewed | en_US |
dc.description.version | publishedVersion | en_US |
dc.rights.holder | Copyright 2022 The Author(s) | en_US |
cristin.ispublished | true | |
cristin.fulltext | original | |
cristin.qualitycode | 1 | |
dc.identifier.doi | 10.4230/LIPIcs.IPEC.2022.8 | |
dc.identifier.cristin | 2099375 | |
dc.source.journal | Leibniz International Proceedings in Informatics | en_US |
dc.source.pagenumber | 8:1-8:18 | en_US |
dc.identifier.citation | Leibniz International Proceedings in Informatics. 2022, 249, 8:1-8:18. | en_US |
dc.source.volume | 249 | en_US |