是否有任何已知的w [3]或w [3] - 哈达问题？

Question

我们目前正在研究一个统治参数的变体，我们已经表明它在W [3]中，参数化复杂性。为了表明它是W [3] -Complete，我们必须展示问题是W [3]硬，即，已经知道已知的W [3]难题。但与W [1]和W [2]不同，在那里证明了许多着名问题，令人惊讶的是，我们遇到了一个难以遇到的一个问题，即使只是在w [3]中也没有困难。当然，我们可以去的一般w [t]案例，但是W [3]的任何结果都会有助于很多。

Answer 1

在较高级别的w-shierarchy 中的自然完全问题。特别地，W [3] -Complete问题 $ p $ -upergraph-（非） - add-set 可能对您有用证明。

鉴于挂钩的问题现在差不多6岁，您可能希望现在有更多的例子。但是，在快速文献搜索中我找不到任何混凝土。我可以找到的最接近的事情是通过查找匹配模式分离串集合几乎总是难以努力的是兰卡岛等人，其中他们猜想他们所说的问题模式识别是w [3] - 为特定参数计算，但这种猜想可能对您的证明不是很有用。我注意到我不是这个领域的专家，所以可能有一些更新的结果，我根本无法找到。