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 - http://www.scopus.com/inward/record.url?scp=85144178889&partnerID=8YFLogxK
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 -