论文标题
关于树结构图上问题的复杂性
On the Complexity of Problems on Tree-structured Graphs
论文作者
论文摘要
在本文中，我们介绍了一类新的参数化问题，我们称之为XALP：可以在$ f（k）n^{o（1）$ time和$ f（k）$ f（k）\ log n $ space中访问的所有参数化问题的类别的类别，可访问非确定性的Turing Mangine，访问辅助元件（只需允许使用辅助元件）。对于此类，“树结构图”上的各种自然问题是完整的：我们显示列表着色和由树宽参数化的全或全部流量为XALP complete。此外，由树宽除以$ \ log n $参数化的独立集和主导集，而由cliquewidth进行了参数的最大切割也是xalp complete。 除了为这些问题找到“自然房屋”外，我们还为未来的减少铺平了道路。我们给出了XALP类的许多等效特征，例如，XALP是通过交替的Turing Machine可以解决的问题类别的类别，其运行的运行最多具有$ f（k）n^{o（1）} $，并使用$ f（k）\ log log n $ n $空间。此外，我们介绍了XALP完整的加权CNF-稳定性和多色集团的“树状”变体。
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 Colouring 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 Multicolour Clique that are XALP-complete.
