Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?

Question

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 (?).

Answer 1

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.