2018 | OriginalPaper | Chapter
Structural Parameterizations of Dominating Set Variants
Authors : Dishant Goyal, Ashwin Jacob, Kaushtubh Kumar, Diptapriyo Majumdar, Venkatesh Raman
Published in: Computer Science – Theory and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
-
we can find a minimum dominating set in \({\mathcal O}^*(3^k)\) time (\({\mathcal O}^*\) notation ignores polynomial factors of input). Within the same time, we can also find a minimum independent dominating set (IDS) or a minimum efficient dominating set (EDS) or a minimum total dominating set. These algorithms are obtained through a dynamic programming approach for an interesting generalization of set cover which may be of independent interest.
-
We complement our upper bound results by showing that at least for dominating set and total dominating set, \({\mathcal O}^*((2-\epsilon )^k)\) time algorithm is not possible for any \(\epsilon > 0\) under, what is known as, Set Cover Conjecture. We also show that most of these variants of dominating set do not have polynomial sized kernel.
-
IDS can be solved in \({\mathcal O}^*(2^k)\) time and we provide an \(\Omega (2^k)\) lower bound under the strong exponential time hypothesis (SETH);
-
the \(2^k\) barrier can be broken for EDS by designing an \({\mathcal O}^*( 3^{k/2})\) algorithm. This is one of the very few problems with a runtime better than \({\mathcal O}^*(2^k)\) in the realm of structural parameterization. We also show that no \(2^{o(k)}\) algorithm is possible unless the exponential time hypothesis (ETH) is false.