On the Impact of Stability and the Helly Property on the Dominating Set Problem
TL;DR
This work shows that -- with a simple change -- in the case of Dominating Set, one can get rid of the stability requirement and result in a fixed-parameter tractable algorithm on exactly those graph classes which do not contain long co-matchings or double-ladders as semi-induced subgraphs.
Abstract
We extend the algorithmic framework of progressive exploration [Fabia\'nski et al., STACS 2019], which yields simple, yet surprisingly general and efficient parameterized algorithms for Dominating Set, Independent Set, and some of their variants. While they identified stability and the Helly property as necessary for their approach, we show that -- with a simple change -- in the case of Dominating Set, one can get rid of the stability requirement. This yields a fixed-parameter tractable algorithm on exactly those graph classes which do not contain long co-matchings or double-ladders as semi-induced subgraphs. Lifting one of these two restrictions makes Dominating Set W[1]-hard on these classes. Our algorithm generalizes results on weakly $\gamma$-closed graphs, and results from Sparsity theory, e.g., nowhere dense and biclique-free classes. At the same time, we match the time complexity of the previously known algorithms on those classes. We demonstrate that this technique can easily be applied to the Distance-$r$ Dominating Set and the Set Cover problem.