3
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • $\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$
    – John Kemeny
    Commented Mar 23, 2016 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
    Commented Mar 23, 2016 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$
    – John Kemeny
    Commented Mar 23, 2016 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$
    – John Kemeny
    Commented Mar 23, 2016 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
    Commented Mar 24, 2016 at 17:43

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.