XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

Hans Bodlaender; Carla Groenland; Hugo Jacob; Lars Jaffke; Paloma Thomé de Lima

doi:10.4230/LIPIcs.IPEC.2022.8

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

Hans Bodlaender
, Carla Groenland
, Hugo Jacob
, Lars Jaffke
, Paloma Thomé de Lima

Algorithms

Research output: Conference Article in Proceeding or Book/Report chapter › Article in proceedings › Research › peer-review

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.

Original language	English
Title of host publication	17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Publication date	2022
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2022.8
Publication status	Published - 2022
Event	International Symposium on Parameterized and Exact Computation - Potsdam, Germany Duration: 7 Sept 2022 → 9 Sept 2022 Conference number: 17

Symposium

Symposium	International Symposium on Parameterized and Exact Computation
Number	17
Country/Territory	Germany
City	Potsdam
Period	07/09/2022 → 09/09/2022

Keywords

XNLP
linear width measures
parameterized complexity
hardness proofs
XP space requirement

Access to Document

10.4230/LIPIcs.IPEC.2022.8Licence: CC BY

Cite this

@inproceedings{9d09c2808f5043e183cdde7259959e19,

title = "XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure",

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 = "XNLP, linear width measures, parameterized complexity, hardness proofs, XP space requirement, XNLP, linear width measures, parameterized complexity, hardness proofs, XP space requirement",

author = "Hans Bodlaender and Carla Groenland and Hugo Jacob and Lars Jaffke and \{Thom{\'e} de Lima\}, Paloma",

year = "2022",

doi = "10.4230/LIPIcs.IPEC.2022.8",

language = "English",

booktitle = "17th International Symposium on Parameterized and Exact Computation (IPEC 2022)",

note = "International Symposium on Parameterized and Exact Computation, IPEC 2022 ; Conference date: 07-09-2022 Through 09-09-2022",

}

Bodlaender, H, Groenland, C, Jacob, H, Jaffke, L & Thomé de Lima, P 2022, XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure. in 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). International Symposium on Parameterized and Exact Computation, Potsdam, Germany, 07/09/2022. https://doi.org/10.4230/LIPIcs.IPEC.2022.8

TY - GEN

T1 - XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

AU - Bodlaender, Hans

AU - Groenland, Carla

AU - Jacob, Hugo

AU - Jaffke, Lars

AU - Thomé de Lima, Paloma

N1 - Conference code: 17

PY - 2022

Y1 - 2022

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 - XNLP

KW - linear width measures

KW - parameterized complexity

KW - hardness proofs

KW - XP space requirement

KW - XNLP

KW - linear width measures

KW - parameterized complexity

KW - hardness proofs

KW - XP space requirement

U2 - 10.4230/LIPIcs.IPEC.2022.8

DO - 10.4230/LIPIcs.IPEC.2022.8

M3 - Article in proceedings

BT - 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)

T2 - International Symposium on Parameterized and Exact Computation

Y2 - 7 September 2022 through 9 September 2022

ER -

XNLP-Completeness for Parameterized Problems on Graphs with a Linear Structure

Abstract

Symposium

Keywords

Access to Document

Fingerprint

Cite this