# W[1]-hard problems on bounded degree graphs

Do you know problems which are W[1]-hard even for bounded degree graphs?

Metric Dimension is hard on graphs with degree at most 3, but it is W[2]-hard. Red-Blue Nonblocker used to be W[1]-hard on bounded degree graphs but there was an error in the proof (book of Downey Fellows 2013), and it is hard only if blue vertices are of bounded degree.

Ball and Trap I remains $W[1]$-hard when restricted to binary trees.

Theorem 5 states:

Theorem 5. Ball and Trap I remains $W[1]$-hard restricted to binary trees, the maximum number of traps per vertex is one per color, and balls are placed on neither leaves nor parents of leaves.

• The link in the answer (which seems dead) is the paper Fellows et al., "On the Multiple Gene Duplication Problem". Aug 11, 2022 at 13:15

Given graphs $G$ and $H$ of maximum degree $2$, it is $\mathsf{W[1]}$-hard to decide whether $G$ contains a subgraph isomorphic to $H$, parameterized by the number of connected components of $G$. This is Theorem N.1 on page 46 of this paper by Dániel Marx and Michał Pilipczuk.

• Thanks! But I'm more interested in results with the natural parameter.
– Olf
Feb 10, 2014 at 9:46