<p>How about Planar Capacitated Dominating Set? It is W[1]-hard (see the paper by Bodlaender, Lokshtanov, Penninkx in IWPEC 2009), but should be solvable in $2^{O(\sqrt{n}\log n)}$ by using the fact that planar graphs have treewidth $O(\sqrt{n})$.</p>

<p>In this problem we are given a graph with integer capacities on the vertices. We are asked to select a minimum size dominating set, with the added restriction that a selected vertex can dominate at most as many of its neighbors as its capacity. Even though the solution is not exactly a subset of $V$, I think it is known that, if we are given a supposed dominating set $D$ we can check if it can be turned into a valid (capacity-respecting) solution in polynomial time by reduction to Max Flow.</p>

CC BY-SA 3.0
2017-02-07T15:36:13.570Z
Many thanks! Technically, this answers my question. But I'd like to wait for a couple of days to see whether there is a better solution (not using weights, capacity, etc.).
Yixin Cao
CC BY-SA 3.0
2017-02-05T18:46:44.717Z
2017-02-05T18:46:44.717Z
Michael Lampis
<p><em>This question is about subset problems (the solution is a subset of the instance, so trivially enumerable in $2^n \cdot n^c$ time), and the parameter is the solution size, so-called the standard parameterization.</em></p>

<p>The answer to the question in the title is obviously yes: the clique problem on sparse graph ($m = O(n)$) remains W[1]-hard but can be trivially solved in $2^{o(n)}$ time. The trick here is that the solution can never be $\omega(\sqrt n)$. So to make the question nontrivial, we have the requirement that</p>

<ul>
<li>$f_k(n)$ is an unbounded function for any $k$, where $f_k(n)$ is the number of instances with instance size $n$ and optimal solution size $k$.</li>
</ul>

<p>Informally speaking, the W[1]-hardness characterizes the hardness of instances with extremely small solutions, while the subexponentional solvability concerns with the solution being almost half of the instance size. So it seems perfectly fine that such a problem exists (?).</p>

CC BY-SA 3.0
2017-02-06T04:46:11.117Z
This is probably my naivete as far as parameterized complexity, but could you explain why padding doesn't work here?
Huck Bennett
CC BY-SA 3.0
2017-02-07T00:10:23.830Z
@RickyDemer Sorry for the typo: It should be $\omega(\sqrt{n})$.
Yixin Cao
<reference-request><parameterized-complexity><exp-time-algorithms>
Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?
Yixin Cao
# Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?

(Asked by: username_0 on 2017-02-05)

*This question is about subset problems (the solution is a subset of the instance, so trivially enumerable in $2^n \cdot n^c$ time), and the parameter is the solution size, so-called the standard parameterization.*

The answer to the question in the title is obviously yes: the clique problem on sparse graph ($m = O(n)$) remains W[1]-hard but can be trivially solved in $2^{o(n)}$ time. The trick here is that the solution can never be $\omega(\sqrt n)$. So to make the question nontrivial, we have the requirement that

* $f\_k(n)$ is an unbounded function for any $k$, where $f\_k(n)$ is the number of instances with instance size $n$ and optimal solution size $k$.

Informally speaking, the W[1]-hardness characterizes the hardness of instances with extremely small solutions, while the subexponentional solvability concerns with the solution being almost half of the instance size. So it seems perfectly fine that such a problem exists (?).

**Tags:** reference-request, parameterized-complexity, exp-time-algorithms
> **Comments:**
> **username_1**: This is probably my naivete as far as parameterized complexity, but could you explain why padding doesn't work here?  
> **username_0**: @RickyDemer Sorry for the typo: It should be $\omega(\sqrt{n})$.  

---

## 1 answers

### Answer by username_2 on 2017-02-05. Score: 6 | Accepted answer

How about Planar Capacitated Dominating Set? It is W[1]-hard (see the paper by Bodlaender, Lokshtanov, Penninkx in IWPEC 2009), but should be solvable in $2^{O(\sqrt{n}\log n)}$ by using the fact that planar graphs have treewidth $O(\sqrt{n})$.

In this problem we are given a graph with integer capacities on the vertices. We are asked to select a minimum size dominating set, with the added restriction that a selected vertex can dominate at most as many of its neighbors as its capacity. Even though the solution is not exactly a subset of $V$, I think it is known that, if we are given a supposed dominating set $D$ we can check if it can be turned into a valid (capacity-respecting) solution in polynomial time by reduction to Max Flow.

> **Comments:**
> **username_0**: Many thanks! Technically, this answers my question. But I'd like to wait for a couple of days to see whether there is a better solution (not using weights, capacity, etc.).  

---

