In this paper, we show that Binary CSP with the size of a vertex cover as parameter is complete for the class W[3]. We obtain a number of related results with variations of the proof techniques, that include: Binary CSP is complete for W[$2d+1$] with as parameter the size of a vertex modulator to graphs of treedepth $c$, or forests of depth $d$, for constant $c\geq 1$, W[$t$]-hard for all $t\in \mathbb{N}$ with treewidth as parameter, and hard for W[SAT] with feedback vertex set as parameter. As corollaries, we give some hardness and membership problems for classes in the W-hierarchy for List Colouring under different parameterisations.
翻译：在本文中,我们显示,W[3]类中具有顶层覆盖大小作为参数的二进制 CSP已经完整。我们取得了若干相关结果,并采用了不同的验证技术,其中包括:二进制 CSP对于W[2d+1美元]是完整的,作为参数,顶层调制器的大小相当于树深度图或深层森林的大小,对于恒定值 $\gq 1美元,对于所有 $t\gin \mathbb{N} 美元来说,W[$t$]-hard,以树宽作为参数,对于W[SAT] 来说是硬的,以反馈顶层设定为参数。作为轮廓,我们给出了不同参数下W-等级的分类的硬性和成员问题。
相关内容
微信扫码咨询专知VIP会员