W [1] -problemas duros en gráficos de grado acotado

11

¿Conoces problemas que son W [1] -duros incluso para gráficos de grados acotados?

La dimensión métrica es difícil en gráficos con un grado máximo de 3, pero es W [2] -duro. Red-Blue Nonblocker solía ser W [1] duro en gráficos de grados limitados, pero hubo un error en la prueba (libro de Downey Fellows 2013), y es difícil solo si los vértices azules son de grado limitado.

Olf
fuente

Respuestas:

7

Ball and Trap I permanece -hardW[1] cuando está restringido a árboles binarios.

El teorema 5 establece:

Teorema 5. Ball and Trap I permanece -duro restringido a árboles binarios, el número máximo de trampas por vértice es uno por color, y las bolas no se colocan ni en las hojas ni en los padres de las hojas.W[1]

Mohammad Al-Turkistany
fuente
5

GH2W[1]GHG

Radu Curticapean
fuente
¡Gracias! Pero estoy más interesado en los resultados con el parámetro natural.
Olf