On the Impact of Stability and the Helly Property on the Dominating Set Problem

arXiv (Cornell University)

Abstract

We extend the algorithmic framework of progressive exploration [Fabiański 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 $γ$-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.

Authors 3

1. Che Cheng
2. Daniel Mock Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University

3. Peter Rossmanith Aachen

   RWTH Aachen University

   Affiliation as printed

   RWTH Aachen University