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.