4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ Why can the solution ​ "never be $\omega(\log n)$" ? ​ ​ ​ ​ $\endgroup$ – user6973 Feb 5 '17 at 14:57
  • 2
    $\begingroup$ This is probably my naivete as far as parameterized complexity, but could you explain why padding doesn't work here? $\endgroup$ – Huck Bennett Feb 6 '17 at 4:46
  • $\begingroup$ @RickyDemer Sorry for the typo: It should be $\omega(\sqrt{n})$. $\endgroup$ – Yixin Cao Feb 7 '17 at 0:10
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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.). $\endgroup$ – Yixin Cao Feb 7 '17 at 15:36

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.