Gibt es noch bekannte W [3] oder W [3] -Hard-Probleme?

Question

Wir arbeiten derzeit an einer Variante des Dominanz-Parameters, und wir haben gezeigt, dass es sich in W [3] in Bezug auf parametrierte Komplexität befindet.Um zu zeigen, dass es W [3] -Complete ist, müssen wir das Problem zeigen, dass W [3] Hart i.e, ein bereits bekanntes W [3] -Tarproblem an uns reduzieren.Im Gegensatz zu W [1] und W [2], in dem viele berühmte Probleme diese Klassen bewährt werden, haben wir überraschenderweise nicht auf ein einziges Problem gestoßen, das wärtet [3] hart und nicht einmal in nur W [3].Natürlich gibt es den allgemeinen W [T] -Toffel, den wir tun können, aber jedes Ergebnis für W [3] würde insbesondere viel helfen.

Answer 1

Es gibt ein paar Beispiele in der Antwort auf natürliche vollständige Probleme in höheren Ebenen der W-Hierarchie . Insbesondere das W [3] -Complete Problem $ P $ -Hypergraph- (nicht) -Dominierungsset kann für Sie nützlich sein Beweis.

In Anbetracht dessen, dass die verlinkte Frage jetzt fast 6 Jahre alt ist, erwarten Sie vielleicht einige weitere Beispiele, um jetzt aufzuspringen. Ich konnte jedoch nichts Konkretes in einer schnellen Literatursuche finden. Das nächste, was ich finden konnte, war Trennen von Sets von Saiten, indem sie passende Muster gefunden haben, die passende Muster fanden, ist fast immer schwer (2017) von Lancia et al., Wo sie Vermutung das für das Problem, das sie anrufen Musteridentifikation ist w [3] -Complace für einen bestimmten Parameter, aber diese Vermutung ist wahrscheinlich nicht sehr nützlich für Ihren Beweis. Ich beachte, dass ich kein Experte auf diesem Gebiet bin, also kann es ein paar jüngere Ergebnisse da draußen sein, ich konnte einfach nicht finden.