Bodlaender, Hans L.
[Author];
Groenland, Carla
[Author];
Jacob, Hugo
[Author];
Pilipczuk, Marcin
[Author];
Pilipczuk, Michał
[Author]
;
Hans L. Bodlaender and Carla Groenland and Hugo Jacob and Marcin Pilipczuk and Michał Pilipczuk
[Contributor]
On the Complexity of Problems on Tree-Structured Graphs
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
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.