11
$\begingroup$

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.

$\endgroup$
7
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! But I'm more interested in results with the natural parameter. $\endgroup$ – Olf Feb 10 '14 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.