Ci sono dei problemi conosciuti [3] o w [3] -hard?

Question

Attualmente stiamo lavorando a una variante del parametro di dominazione e abbiamo dimostrato che è in W [3] per quanto riguarda la complessità parametrizzata.Per mostrare che è w [3] -Complete, dobbiamo dimostrare che il problema è W [3] HARD I.e, riduci un problema difficile già conosciuto [3] al nostro.Ma a differenza di W [1] e w [2], dove molti problemi famosi sono dimostrati quelle classi, sorprendentemente non abbiamo incontrato un singolo problema che è W [3] HARD e nemmeno in Solo W [3].Naturalmente c'è il caso General W [T] che possiamo andare, ma qualsiasi risultato per W [3] in particolare aiuterà molto.

Answer 1

Ci sono alcuni esempi nella risposta a problemi completi naturali nei livelli più alti della w-gerarchia . In particolare, il problema W [3] -Completo $ p $ -hypergraph- (non)--dominating-set potrebbe essere utile per il tuo Prova.

Dato che la domanda collegata è ora quasi 6 anni, forse ti aspetteresti che alcuni esempi si trovino ormai. Tuttavia, non sono riuscito a trovare nulla di concreto in una rapida ricerca della letteratura. La cosa più vicina che ho trovato era Separare i set di stringhe trovando modelli di corrispondenza è quasi sempre dura (2017) di Lancia et al., Dove sono congetture che il problema che chiamano Identificazione del modello è w [3] -Complete per un particolare parametro, ma questa congettura non è probabilmente molto utile per la tua prova. Prendo nota che non sono un esperto in questo campo, quindi potrebbero esserci alcuni risultati più recenti là fuori, semplicemente non sono stato in grado di trovare.