W [1] - twarde problemy na wykresach ze stopniem granicznym

Czy znasz problemy, które są twarde W [1], nawet w przypadku wykresów o ograniczonym stopniu?

Wymiar metryczny jest trudny na wykresach ze stopniem co najwyżej 3, ale ma twardość W [2]. Czerwono-niebieski Nonblocker był twardy W [1] na wykresach ze stopniem ograniczonym, ale wystąpił błąd w dowodzie (książka Downey Fellows 2013) i jest to trudne tylko wtedy, gdy niebieskie wierzchołki mają ograniczony stopień.

Piłka i pułapka I pozostają twarde $W[1]$ gdy są ograniczone do drzew podwójnych.

Twierdzenie 5 stwierdza:

Twierdzenie 5. Piłka i pułapka I pozostają twarde twarde ograniczone do drzew podwójnych, maksymalna liczba pułapek na wierzchołek wynosi jeden na kolor, a kule nie są umieszczane ani na liściach, ani na rodzicach liści.$W[1]$

$G$$H$$2$$\mathsf{W[1]}$$G$$H$$G$