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 (?).
Is there a W[1]-hard problem that can be solved in $2^{o(n)}$ time?
reference request;parameterized complexity;exp time algorithms