# Parameterized Dominating Set

What is the best algorithm to compute p-dominating set?

The p-dominating set problem is a parameterized version of minimum dominating set in which the problem takes a parameter $k$ also as an input, and the problem is now whether there exist a dominating set of cardinality at most $k$.

I know the problem is W-hard so there is no chance of getting a $f(k) n^c$ running time algorithm unless the parameterized hierarchy collapses.

• It is W-compete, yes, but if you know something about your input instances, it might actually be much simpler. See a loooong list of problems and their domination complexity on graphclasses.org. Mar 23 '16 at 11:08
• Yes, I am looking for this problem on sparse graphs. I just wanted to analyze some known algorithm over sparse graph. Mar 23 '16 at 13:26
• For sparse graphs it might be much easier (depending on your definition of sparse), as it even admits a linear kernel (disclaimer: am author), and thus is very much FPT. Mar 23 '16 at 13:31
• By the way, if the input graphs are degenerate, there is a very simple fpt branching algorithm: Pick a low degree undominated vertex, either that vertex has to be in the solution, or a subset of its neighbors. Mark dominated vertices, delete the low degree one and repeat. Mar 23 '16 at 20:29
• yeah, I agree with the degenerate graph solution actually its exactly same for planner graph as the planner graph are 5-degenerate. Thanks for the link. Mar 24 '16 at 17:43

Well, you can always solve it in XP time by trying all possible $k$-sets. In fact, it was shown by Pătraşcu and Williams  that there is no $O(n^{k-\varepsilon})$-time algorithm for $k$-dominating set for any $\varepsilon > 0$, assuming SETH.
This is almost tight as for $k \geq 7$, the problem can be solved in $n^{k+o(1)}$ time (see ). As a special case, you can solve 2-dominating set in $O(n^\omega)$ time, where $\omega < 2.376$ using matrix multiplication.