论文标题
二进制CSP的参数化复杂性：顶点覆盖，TreeDepth和相关参数
Parameterized Complexity of Binary CSP: Vertex Cover, Treedepth, and Related Parameters
论文作者
论文摘要
我们研究了通过顶点覆盖号和约束图的TREEDEPTH的参数CSP的参数化复杂性，以及通过选择相关调节器的参数的选择。主要发现如下： i）由顶点封面参数化的二进制CSP为$ \ mathrm {w} [3] $ - 完成。更一般而言，对于每个正整数$ d $，由调制器的大小到Treedepth-d Graph的二进制CSP为$ \ mathrm {w} [2d+1] $ - 完成。这提供了一个新的自然问题家族，这些家庭对于W层次结构的奇数水平都是完整的。 ii）我们引入了一个新的复杂性类XSLP，该类别定义，以便该类别由Treedeppth参数化的二进制CSP已完成。我们提供了XSLP的两个等效特征：第一个将XSLP与交替的Turing Machine的模型相关联，对Cononderminism和空间复杂性有一定的限制，而第二个将XSLP连接到了模型检查一阶逻辑问题和适当限制的通用通用量化的问题。有趣的是，XSLP的机器表征的证据使用了通用树的概念，这在最近的奇偶校验游戏中是显着的 iii）我们描述了一个夹在W层和A层之间的新复杂性层次结构：对于每一个奇数$ t $，我们将参数化的复杂性类$ \ mathrm {s} [t] $与$ \ mathrm {w} [w} [t] \ mathrm {a} [t] $，使用在顶点封面编号和TreeDeppth之间插值的参数定义。 我们预计，许多研究类都将在未来有用，以指出图形问题的各种结构参数的复杂性。
We investigate the parameterized complexity of Binary CSP parameterized by the vertex cover number and the treedepth of the constraint graph, as well as by a selection of related modulator-based parameters. The main findings are as follows: i) Binary CSP parameterized by the vertex cover number is $\mathrm{W}[3]$-complete. More generally, for every positive integer $d$, Binary CSP parameterized by the size of a modulator to a treedepth-d graph is $\mathrm{W}[2d+1]$-complete. This provides a new family of natural problems that are complete for odd levels of the W-hierarchy. ii) We introduce a new complexity class XSLP, defined so that Binary CSP parameterized by treedepth is complete for this class. We provide two equivalent characterizations of XSLP: the first one relates XSLP to a model of an alternating Turing machine with certain restrictions on conondeterminism and space complexity, while the second one links XSLP to the problem of model-checking first-order logic with suitably restricted universal quantification. Interestingly, the proof of the machine characterization of XSLP uses the concept of universal trees, which are prominently featured in the recent work on parity games iii) We describe a new complexity hierarchy sandwiched between the W-hierarchy and the A-hierarchy: For every odd $t$, we introduce a parameterized complexity class $\mathrm{S}[t]$ with $\mathrm{W}[t]\subseteq \mathrm{S}[t]\subseteq \mathrm{A}[t]$, defined using a parameter that interpolates between the vertex cover number and the treedepth. We expect that many of the studied classes will be useful in the future for pinpointing the complexity of various structural parameterizations of graph problems.
