Enumerating Minimal Connected Dominating Sets
Faisal N. Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff, Kevin J. Mann · SIAM Journal on Discrete Mathematics · 2025
Abstract. The question to enumerate all (inclusionwise) minimal connected dominating sets in a graph of order [Formula: see text] in time significantly less than [Formula: see text] is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time [Formula: see text], using polynomial space only. The key to this result is the consideration of this enumeration problem on 2-degenerate graphs, which is proven to be possible in time [Formula: see text]. Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order [Formula: see text] with [Formula: see text] many minimal connected dominating sets, while previous examples achieved [Formula: see text]. Our example happens to yield 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are [Formula: see text] and [Formula: see text], respectively. We also address essential questions concerning output-sensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much effort. More precisely, we prove that it is NP -complete to decide, given a graph [Formula: see text] and a vertex set [Formula: see text], if there exists a minimal connected dominating set [Formula: see text] with [Formula: see text], even if [Formula: see text] is known to be 2-degenerate. Our reduction also shows that even any subexponential delay is not easy to achieve for enumerating minimal connected dominating sets. Another reduction shows that no FPT -algorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by [Formula: see text]. This also adds one more problem to the still rather few natural parameterized problems that are complete for the parameterized complexity class W [3]. We also relate our enumeration problem to the famous Hitting Set Transversal problem, a problem open for more than four decades, which can be phrased in our context as the question to enumerate all minimal dominating sets of a graph with polynomial delay, by showing that a polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic (polynomial-delay) solution to the Hitting Set Transversal problem.