Dominating set of given size $k$ in $O(2^k |V| |E|)$

Question

Recently I've encountered an interesting case of dominating set problem: given an unweighted and undirected graph $G(V, E)$ and knowing that it contains a dominating set of size $k$, find any such dominating set in time $O(2^k\ \vert V \vert\ \vert E \vert)$.

During my research, I found only some algorithms to find fixed-size dominating set in a $d$-degenerated graphs, but no such restriction is applied in this problem.

Is there any way to solve that problem in such time?

Answer 1

It is well-known (for a very specific group of people) that dominating set is W[2]-complete (for undirected graphs).

You are asking for a fixed-parameter tractable algorithm for solving dominating set in general graphs. The class of algorithms admitting such running times comprises the class called FPT.

Unfortunately, most people in the aforementioned group believe that FPT is a strict subset of W[1] which again is a strict subset of W[2].

To summarize, we don't think that Dominating Set has an FPT algorithm.

Under the assumption that $\text{FPT} \neq \text{W[2]}$, there is no $O(f(k) \cdot \text{poly}(|V|, |E|)$ algorithm for any function $f$ and any polynomial function $\text{poly}$.

For the Vertex Cover problem, there is such an algorithm, that is, Vertex Cover is in FPT. Clique and Independent Set are W[1]-complete, whereas Chromatic Number is in XP, which means that it is above the entire W-hierarchy.

Why guarantees of yes-instances won't help

Let $A$ be an algorithm that in running time $f(x)$ (where $x$ is the size of the input) returns a solution of size at most $k$. Algorithm $A$ only works on "yes"-instances. Create an algorithm $A′$ that takes any input, runs $A$ for $f(x)$ steps, and if $A$ hasn't terminated, returns "no". If $A$ returns, $A′$ verifies the solution (in polynomial time) and outputs either "yes" or "no" according to $A$s output.

The algorithm $A$ is an algorithm, so it's not likely to get mad at you for trying to cheat; it has to do something for any input, possibly crash and go up in smoke, but there is a nice dichotomy we can use to cheat:

• If $A$ gives you any output, we can verify that the output is a correct solution in polynomial time
• If $A$ fails to give you any (correct) output in its specified running time, the input has to be a no instance.

Hence, if an algorithm works on guaranteed yes-instances, we can create an algorithm that works on any instance.