AbuKhzam, Faisal N. ;
Fernau, Henning ;
Gras, Benjamin ;
Liedloff, Mathieu ;
Mann, Kevin
Enumerating Minimal Connected Dominating Sets
Abstract
The question to enumerate all (inclusionwise) minimal connected dominating sets in a graph of order n in time significantly less than 2ⁿ is an open question that was asked in many places. We answer this question affirmatively, by providing an enumeration algorithm that runs in time 𝒪(1.9896ⁿ), using polynomial space only. The key to this result is the consideration of this enumeration problem on 2degenerate graphs, which is proven to be possible in time 𝒪(1.9767ⁿ). Apart from solving this old open question, we also show new lower bound results. More precisely, we construct a family of graphs of order n with Ω(1.4890ⁿ) many minimal connected dominating sets, while previous examples achieved Ω(1.4422ⁿ). Our example happens to yield 4degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2degenerate and of 3degenerate graphs, which are Ω(1.3195ⁿ) and Ω(1.4723ⁿ), respectively.
We also address essential questions concerning outputsensitive enumeration. Namely, we give reasons why our algorithm cannot be turned into an enumeration algorithm that guarantees polynomial delay without much efforts. More precisely, we prove that it is NPcomplete to decide, given a graph G and a vertex set U, if there exists a minimal connected dominating set D with U ⊆ D, even if G is known to be 2degenerate. 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 FPTalgorithms can be expected for this extension problem concerning minimal connected dominating sets, parameterized by U. This also adds one more problem to the still rather few natural parameterized problems that are complete for the class W[3]. We also relate our enumeration problem to the famous open Hitting Set Transversal problem, 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 polynomialdelay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic solution to the Hitting Set Transversal problem.
BibTeX  Entry
@InProceedings{abukhzam_et_al:LIPIcs.ESA.2022.1,
author = {AbuKhzam, Faisal N. and Fernau, Henning and Gras, Benjamin and Liedloff, Mathieu and Mann, Kevin},
title = {{Enumerating Minimal Connected Dominating Sets}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {1:11:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16939},
URN = {urn:nbn:de:0030drops169390},
doi = {10.4230/LIPIcs.ESA.2022.1},
annote = {Keywords: enumeration problems, connected domination, degenerate graphs}
}
01.09.2022
Keywords: 

enumeration problems, connected domination, degenerate graphs 
Seminar: 

30th Annual European Symposium on Algorithms (ESA 2022)

Issue date: 

2022 
Date of publication: 

01.09.2022 