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[2]-hard so there is no chance of getting a $f(k) n^c$ running time algorithm unless the parameterized hierarchy collapses.

  • $\begingroup$ It is W[2]-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. $\endgroup$
    – Pål GD
    Mar 23 '16 at 11:08
  • $\begingroup$ Yes, I am looking for this problem on sparse graphs. I just wanted to analyze some known algorithm over sparse graph. $\endgroup$
    – Thinking
    Mar 23 '16 at 13:26
  • 1
    $\begingroup$ 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. $\endgroup$
    – Pål GD
    Mar 23 '16 at 13:31
  • $\begingroup$ 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. $\endgroup$
    – Pål GD
    Mar 23 '16 at 20:29
  • $\begingroup$ 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. $\endgroup$
    – Thinking
    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 [1] 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 [1]). As a special case, you can solve 2-dominating set in $O(n^\omega)$ time, where $\omega < 2.376$ using matrix multiplication.

[1] Pătraşcu, Mihai, and Ryan Williams. "On the possibility of faster SAT algorithms." Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. 2010.


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.