Y a-t-il des problèmes connus W [3] ou W [3]?

Question

Nous travaillons actuellement sur une variante de paramètre de domination et nous avons montré qu'il est dans W [3] en ce qui concerne la complexité paramétrée.Pour montrer que c'est w [3] -Compléte, nous devons montrer le problème est W [3] HARD I.E, réduisez un problème déjà connu W [3] un problème difficile à la nôtre.Mais contrairement à W [1] and w [2], où de nombreux problèmes célèbres sont prouvés ces classes, surprenant, nous n'avons pas rencontré un seul problème qui est difficile et même dans seulement et même dans seulement W [3].Bien sûr, il y a le dossier général W [T] que nous pouvons faire, mais tout résultat pour W [3] en particulier aiderait beaucoup.

Answer 1

Il y a quelques exemples dans la réponse à problèmes naturels complets dans des niveaux supérieurs de la hiérarchie W-Hiérarchie . En particulier, le problème W [3] -Complete $ P $ -hypergraphe- (non) -dominateur-set peut être utile pour votre Preuve.

Étant donné que la question liée est de plus de 6 ans, vous m'attendez peut-être que d'autres exemples apparaissent maintenant. Cependant, je n'ai trouvé rien de concret dans une recherche rapide de la littérature. La chose la plus proche que je puisse trouver était séparant des ensembles de cordes en trouvant des modèles de correspondance est presque toujours difficile (2017) de Lancia et al., Où ils sont conjectures que le problème qu'ils appellent IDENTIFICATION DES MOTIFS W [3] -COMPLETE Pour un paramètre particulier, mais cette conjecture n'est probablement pas très utile pour votre preuve. Je note que je ne suis pas un expert dans ce domaine, il peut donc y avoir des résultats plus récents, je n'ai tout simplement pas été capable de trouver.