On the Impact of Stability and the Helly Property on the Dominating Set Problem
2026-07-20 • Data Structures and Algorithms
Data Structures and AlgorithmsComputational ComplexityDiscrete Mathematics
AI summaryⓘ
The authors improved an existing method for solving the Dominating Set problem, which involves selecting important points in a network to cover all others. They removed a previously needed condition called stability, expanding the types of graphs where their approach works efficiently. Their method handles graphs without certain complicated structures and matches the speed of known algorithms for special graph classes. They also show their approach can be adapted to related problems like Distance-r Dominating Set and Set Cover.
Dominating Setparameterized algorithmsstabilityHelly propertyco-matchingsdouble-laddersfixed-parameter tractablenowhere dense graphsSet CoverDistance-r Dominating Set
Authors
Che Cheng, Daniel Mock, Peter Rossmanith
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.