W-Hierarchies Defined by Symmetric Gates
W-Hierarchies Defined by Symmetric Gates
复制标题
DOI：
10.1007/s00224-008-9138-6
复制
发表时间：
2010-02
影响因子：
0.5
通讯作者：
M. Fellows;J. Flum;D. Hermelin;M. Müller;Frances A. Rosamond
中科院分区：
文献类型：
--
作者：
M. Fellows;J. Flum;D. Hermelin;M. Müller;Frances A. Rosamond
W-层次类是参数复杂性中最重要的一类难解问题。这些类最初是通过布尔电路的加权可满足性问题定义的。在这里，除了布尔连接词之外，我们还认为连接词是多数、不全部相等和唯一的。例如，由多数连接输出结构标记的门，如果其输入的一半以上为真。对于任意有限的连接词集合，我们构造了相应的W()-层次。我们得到了保证W-谱系和W()-谱系水平重合的一般条件。如果只包含多数连接词，则层次结构的第一级重合。我们利用这一点证明了参数化点覆盖问题的一个变种，即多数点覆盖问题是W[1]-完全的。
The classes of the W-hierarchy are the most important classes of intractable problems in parameterized complexity. These classes were originally defined via the weighted satisfiability problem for Boolean circuits. Here, besides the Boolean connectives we consider connectives such asmajority,not-all-equal, andunique. For example, a gate labelled by the majority connective outputstrueif more than half of its inputs aretrue. For any finite setof connectives we construct the corresponding W()-hierarchy. We derive some general conditions which guarantee that the W-hierarchy and the W()-hierarchy coincide levelwise. Ifonly contains the majority connective then the first levels of the hierarchies coincide. We use this to show that a variant of the parameterized vertex cover problem, the majority vertex cover problem, is W[1]-complete.