On the Complexity of Problems on Tree-Structured Graphs

Hans L. Bodlaender; Carla Groenland; Hugo Jacob; Marcin Pilipczuk; Michał Pilipczuk

doi:10.4230/LIPIcs.IPEC.2022.6

On the Complexity of Problems on Tree-Structured Graphs

Hans L. Bodlaender^*, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, Michał Pilipczuk

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

Abstract

In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)n^O(1) time and f(k) log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on “tree-structured graphs” are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a “natural home” for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)n^O(1) and use f(k) log n space. Moreover, we introduce “tree-shaped” variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.

Original language	English
Title of host publication	17th International Symposium on Parameterized and Exact Computation, IPEC 2022
Editors	Holger Dell, Jesper Nederlof
Publisher	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Pages	6:1-6:17
Number of pages	17
ISBN (Electronic)	9783959772600
ISBN (Print)	9783959772600
DOIs	https://doi.org/10.4230/LIPIcs.IPEC.2022.6
Publication status	Published - 1 Dec 2022
Event	17th International Symposium on Parameterized and Exact Computation, IPEC 2022 - Potsdam, Germany Duration: 7 Sept 2022 → 9 Sept 2022

Publication series

Name	Leibniz International Proceedings in Informatics, LIPIcs
Volume	249
ISSN (Print)	1868-8969

Conference

Conference	17th International Symposium on Parameterized and Exact Computation, IPEC 2022
Country/Territory	Germany
City	Potsdam
Period	7/09/22 → 9/09/22

Bibliographical note

Funding Information:
Funding Carla Groenland: Supported by the European Union’s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Skłodowska-Curie grant GRAPHCOSY (number 101063180). Marcin Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 714704. Michał Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 948057.

Publisher Copyright:
© Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk.

Funding

Funding Carla Groenland: Supported by the European Union’s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Skłodowska-Curie grant GRAPHCOSY (number 101063180). Marcin Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 714704. Michał Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 948057.

Keywords

Parameterized Complexity
Treewidth
XALP
XNLP

Access to Document

10.4230/LIPIcs.IPEC.2022.6Licence: CC BY

LIPIcs-IPEC-2022-6Final published version, 1.03 MBLicence: CC BY

Cite this

Bodlaender, H. L., Groenland, C., Jacob, H., Pilipczuk, M., & Pilipczuk, M. (2022). On the Complexity of Problems on Tree-Structured Graphs. In H. Dell, & J. Nederlof (Eds.), 17th International Symposium on Parameterized and Exact Computation, IPEC 2022 (pp. 6:1-6:17). Article 6 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 249). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.IPEC.2022.6

Bodlaender, Hans L. ; Groenland, Carla ; Jacob, Hugo et al. / On the Complexity of Problems on Tree-Structured Graphs. 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. editor / Holger Dell ; Jesper Nederlof. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. pp. 6:1-6:17 (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{1d4c9b684a9e441ab4ebf56462bbdf5b,

title = "On the Complexity of Problems on Tree-Structured Graphs",

abstract = "In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)nO(1) time and f(k) log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on “tree-structured graphs” are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a “natural home” for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)nO(1) and use f(k) log n space. Moreover, we introduce “tree-shaped” variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.",

keywords = "Parameterized Complexity, Treewidth, XALP, XNLP",

author = "Bodlaender, \{Hans L.\} and Carla Groenland and Hugo Jacob and Marcin Pilipczuk and Micha{\l} Pilipczuk",

note = "Funding Information: Funding Carla Groenland: Supported by the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Sk{\l}odowska-Curie grant GRAPHCOSY (number 101063180). Marcin Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme Grant Agreement 714704. Micha{\l} Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme Grant Agreement 948057. Publisher Copyright: {\textcopyright} Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Micha{\l} Pilipczuk.; 17th International Symposium on Parameterized and Exact Computation, IPEC 2022 ; Conference date: 07-09-2022 Through 09-09-2022",

year = "2022",

month = dec,

day = "1",

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

language = "English",

isbn = "9783959772600",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",

pages = "6:1--6:17",

editor = "Holger Dell and Jesper Nederlof",

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

address = "Germany",

}

Bodlaender, HL, Groenland, C, Jacob, H, Pilipczuk, M & Pilipczuk, M 2022, On the Complexity of Problems on Tree-Structured Graphs. in H Dell & J Nederlof (eds), 17th International Symposium on Parameterized and Exact Computation, IPEC 2022., 6, Leibniz International Proceedings in Informatics, LIPIcs, vol. 249, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, pp. 6:1-6:17, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022, Potsdam, Germany, 7/09/22. https://doi.org/10.4230/LIPIcs.IPEC.2022.6

On the Complexity of Problems on Tree-Structured Graphs. / Bodlaender, Hans L.; Groenland, Carla; Jacob, Hugo et al.
17th International Symposium on Parameterized and Exact Computation, IPEC 2022. ed. / Holger Dell; Jesper Nederlof. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. p. 6:1-6:17 6 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 249).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the Complexity of Problems on Tree-Structured Graphs

AU - Bodlaender, Hans L.

AU - Groenland, Carla

AU - Jacob, Hugo

AU - Pilipczuk, Marcin

AU - Pilipczuk, Michał

N1 - Funding Information: Funding Carla Groenland: Supported by the European Union’s Horizon 2020 research and innovation programme under the ERC grant CRACKNP (number 853234) and the Marie Skłodowska-Curie grant GRAPHCOSY (number 101063180). Marcin Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 714704. Michał Pilipczuk: This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme Grant Agreement 948057. Publisher Copyright: © Hans L. Bodlaender, Carla Groenland, Hugo Jacob, Marcin Pilipczuk, and Michał Pilipczuk.

PY - 2022/12/1

Y1 - 2022/12/1

N2 - In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)nO(1) time and f(k) log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on “tree-structured graphs” are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a “natural home” for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)nO(1) and use f(k) log n space. Moreover, we introduce “tree-shaped” variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.

AB - In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in f(k)nO(1) time and f(k) log n space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on “tree-structured graphs” are complete for this class: we show that List Coloring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by log n, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a “natural home” for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most f(k)nO(1) and use f(k) log n space. Moreover, we introduce “tree-shaped” variants of Weighted CNF-Satisfiability and Multicolor Clique that are XALP-complete.

KW - Parameterized Complexity

KW - Treewidth

KW - XALP

KW - XNLP

UR - https://www.scopus.com/pages/publications/85144178889

U2 - 10.4230/LIPIcs.IPEC.2022.6

DO - 10.4230/LIPIcs.IPEC.2022.6

M3 - Conference contribution

AN - SCOPUS:85144178889

SN - 9783959772600

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 6:1-6:17

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

A2 - Dell, Holger

A2 - Nederlof, Jesper

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 17th International Symposium on Parameterized and Exact Computation, IPEC 2022

Y2 - 7 September 2022 through 9 September 2022

ER -

Bodlaender HL, Groenland C, Jacob H, Pilipczuk M, Pilipczuk M. On the Complexity of Problems on Tree-Structured Graphs. In Dell H, Nederlof J, editors, 17th International Symposium on Parameterized and Exact Computation, IPEC 2022. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2022. p. 6:1-6:17. 6. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.IPEC.2022.6

On the Complexity of Problems on Tree-Structured Graphs

Abstract

Publication series

Conference

Bibliographical note

Funding

Keywords

Access to Document

Other files and links

Fingerprint

Cite this