2026-07-22T04:54:19Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17362 2024-03-06T10:59:33Z ddc:004 open_access

On the Complexity of Problems on Tree-Structured Graphs Bodlaender, Hans L. Groenland, Carla Jacob, Hugo Pilipczuk, Marcin Pilipczuk, Michał Parameterized Complexity Treewidth XALP XNLP 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Hans L. Bodlaender and Carla Groenland and Hugo Jacob and Marcin Pilipczuk and Michał Pilipczuk 2022 Is Part Of LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.IPEC.2022.6 urn:nbn:de:0030-drops-173626 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.6 eng https://creativecommons.org/licenses/by/4.0/legalcode