patternMinor
Parameterized Dominating Set
Viewed 0 times
parameterizedsetdominating
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#54751, answer score: 4
Revisions (0)
No revisions yet.