知られているW [3]またはW [3] - ハードの問題はありますか？

Question

現在、支配パラメータの変種に取り組んでおり、パラメータ化された複雑さに関してはW [3]にあることがわかりました。それを示すためにそれをw [3] - Completeであることは、問題を示す必要がありますw [3]私たちのものに既知のW [3]難しい問題を減らす。しかし、W [1]とW [2]とは異なり、多くの有名な問題がそれらのクラスであることが証明されている、驚くべきことに、私たちはW [3]である単一の問題に出かけていない[3]。もちろん、私たちが行くことができる一般的なW [T]ケースがありますが、特にW [3]の結果はたくさん役立ちます。

Answer 1

の高レベルのW-hierarchy には、答えにいくつかの例があります。特に、w [3] -Complete問題 $ p $ -hypergraph-（非） - dotrimating-set はあなたにとって有用であるかもしれません。証明書。

リンクされた質問が今後6歳であることを考えると、あなたはおそらく今ではもう少し上にポップアップすることを期待しています。しかし、私は素早い文献検索でコンクリートは何も見つけることができませんでした。私が見つけることができる最も近いものは、整合パターンを見つけることによって弦のセットを分離することで、ほとんど常に難しい（2017）によって、Lancia et al。推測彼らが呼ぶ問題パターン識別は、特定のパラメータの場合はW [3]ですが、この推測はおそらくあなたの証明にはあまり役に立ちません。私はこの分野の専門家ではないので、私は単に見つけることができなかったいくつかの最近の結果があるかもしれません。