<p>Ball and Trap I remains <a href="http://taxonomy.zoology.gla.ac.uk/rod/genetree/maths/fellows.pdf">$W[1]$-hard</a> when restricted to binary trees.</p>

<p>Theorem 5 states:</p>

<blockquote>
  <p>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.</p>
</blockquote>

CC BY-SA 4.0
2022-08-11T13:15:34.163Z
The link in the answer (which seems dead) is the paper Fellows et al., "On the Multiple Gene Duplication Problem".
Cyriac Antony
CC BY-SA 3.0
2014-02-06T15:55:08.407Z
2014-02-06T16:07:57.700Z
2014-02-06T16:07:57.700Z
Mohammad Al-Turkistany
<p>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 <a href="http://arxiv.org/abs/1307.2187" rel="noreferrer">this paper</a> by Dániel Marx and Michał Pilipczuk.</p>

CC BY-SA 3.0
2014-02-10T09:46:24.977Z
Thanks! But I'm more interested in results with the natural parameter.
Olf
CC BY-SA 3.0
2014-02-08T00:35:59.597Z
2014-02-08T00:35:59.597Z
Radu Curticapean
<p>Do you know problems which are W[1]-hard even for bounded degree graphs? </p>

<p>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.</p>

<reference-request><parameterized-complexity>
W[1]-hard problems on bounded degree graphs
Olf
# W[1]-hard problems on bounded degree graphs

(Asked by: username_0 on 2014-02-06)

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.

**Tags:** reference-request, parameterized-complexity


---

## 2 answers

### Answer by username_1 on 2014-02-06. Score: 7

Ball and Trap I remains [$W[1]$-hard](http://taxonomy.zoology.gla.ac.uk/rod/genetree/maths/fellows.pdf) 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.

> **Comments:**
> **username_2**: The link in the answer (which seems dead) is the paper Fellows et al., "On the Multiple Gene Duplication Problem".  

---

### Answer by username_3 on 2014-02-08. Score: 5

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](http://arxiv.org/abs/1307.2187) by Dániel Marx and Michał Pilipczuk.

> **Comments:**
> **username_0**: Thanks! But I'm more interested in results with the natural parameter.  

---

