¿Hay algún problema conocido W [3] o W [3] -Hard?

Question

Actualmente estamos trabajando en una variante del parámetro de dominación y hemos demostrado que está en W [3] con respecto a la complejidad parametrizada.Para demostrar que es W [3] -clase, debemos mostrar el problema es que es más difícil, es difícil, reducir un problema duro ya conocido con el nuestro.Pero a diferencia de W [1] y W [2], donde muchos problemas famosos se prueban esas clases, sorprendentemente, no hemos encontrado un solo problema que es w [3] duro y ni siquiera en Just W [3].Por supuesto, existe el caso general W [t] en el que podemos ir, pero cualquier resultado para W [3] en particular ayudaría mucho.

Answer 1

Hay algunos ejemplos en la respuesta a Problemas naturales completos en niveles más altos de la jerabia W-Jerarquía . En particular, el problema W [3] -clase $ p $ -hypergraft- (no) -dominating-set puede ser útil para su prueba.

Dado que la pregunta vinculada ya está a casi 6 años de edad, quizás esperará que los ejemplos más se presenten. Sin embargo, no pude encontrar nada concreto en una búsqueda rápida de literatura. Lo más cercano que pude encontrar fue Separando conjuntos de cuerdas al encontrar patrones de coincidencia casi siempre es difícil (2017) por Lancia et al., Donde ellos conjeture que llaman Pattern Identification es W [3] -Complete para un parámetro en particular, pero esta conjetura probablemente no sea muy útil para su prueba. Nota que no soy un experto en este campo, por lo que puede haber algunos resultados más recientes que simplemente no pude encontrar.