Document Open Access Logo

Enumerating Minimal Connected Dominating Sets

Authors Faisal N. Abu-Khzam , Henning Fernau , Benjamin Gras , Mathieu Liedloff , Kevin Mann

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.1.pdf
  • Filesize: 0.83 MB
  • 15 pages

Document Identifiers

Author Details

Faisal N. Abu-Khzam
  • Department of Computer Science and Mathematics, Lebanese American University, Beirut, Lebanon
Henning Fernau
  • Fachbereich IV, Informatikwissenschaften, Universität Trier, Germany
Benjamin Gras
  • Université d'Orléans, INSA Centre Val de Loire, LIFO EA 4022, France
Mathieu Liedloff
  • Université d'Orléans, INSA Centre Val de Loire, LIFO EA 4022, France
Kevin Mann
  • Fachbereich IV, Informatikwissenschaften, Universität Trier, Germany

Acknowledgements

Henning Fernau likes to thank the Université d'Orléans for inviting him as a professeur invité in 2021; on these visits, much of the research was started.

Cite As Get BibTex

Faisal N. Abu-Khzam, Henning Fernau, Benjamin Gras, Mathieu Liedloff, and Kevin Mann. Enumerating Minimal Connected Dominating Sets. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 1:1-1:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.ESA.2022.1

Abstract

The question to enumerate all (inclusion-wise) 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 2-degenerate 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 4-degenerate graphs. Additionally, we give lower bounds for the previously not considered classes of 2-degenerate and of 3-degenerate graphs, which are Ω(1.3195ⁿ) and Ω(1.4723ⁿ), 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 efforts. More precisely, we prove that it is NP-complete 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 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 |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 polynomial-delay enumeration algorithm for minimal connected dominating sets implies an affirmative algorithmic solution to the Hitting Set Transversal problem.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
Keywords
  • enumeration problems
  • connected domination
  • degenerate graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. F. N. Abu-Khzam, H. Fernau, B. Gras, M. Liedloff, and K. Mann. Enumerating connected dominating sets. Technical report, Cornell University, ArXiv/CoRR, 2022. URL: https://doi.org/10.48550/arXiv.2205.00086.
  2. F. N. Abu-Khzam, H. Fernau, and K. Mann. Minimal Roman dominating functions: Extensions and enumeration. Technical Report 2204.04765, Cornell University, ArXiv/CoRR, 2022. To appear in the Proceedings of WG 2022. URL: https://doi.org/10.48550/arXiv.2204.04765.
  3. F. N. Abu-Khzam, A. E. Mouawad, and M. Liedloff. An exact algorithm for connected red-blue dominating set. Journal of Discrete Algorithms, 9(3):252-262, 2011. Google Scholar
  4. T. Bläsius, T. Friedrich, J. Lischeid, K. Meeks, and M. Schirneck. Efficiently enumerating hitting sets of hypergraphs arising in data profiling. Journal of Computer and System Sciences, 124:192-213, 2022. Google Scholar
  5. T. Bläsius, T. Friedrich, and M. Schirneck. The complexity of dependency detection and discovery in relational databases. Theoretical Computer Science, 900:79-96, 2022. Google Scholar
  6. H. L. Bodlaender, E. Boros, P. Heggernes, and D. Kratsch. Open problems of the Lorentz workshop "Enumeration algorithms using structure". Technical Report UU-CS-2015-016, Department of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands, November 2015. Google Scholar
  7. K. Casel, H. Fernau, M. Khosravian Ghadikolaei, J. Monnot, and F. Sikora. On the complexity of solution extension of optimization problems. Theoretical Computer Science, 904:48-65, 2022. Google Scholar
  8. J. Chen and F. Zhang. On product covering in 3-tier supply chain models: Natural complete problems for W[3] and W[4]. Theoretical Computer Science, 363(3):278-288, 2006. Google Scholar
  9. J.-F. Couturier, P. Heggernes, P. van 't Hof, and D. Kratsch. Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. In M. Bieliková, G. Friedrich, G. Gottlob, S. Katzenbeisser, and G. Turán, editors, SOFSEM 2012: Theory and Practice of Computer Science - 38th Conference on Current Trends in Theory and Practice of Computer Science, volume 7147 of LNCS, pages 202-213. Springer, 2012. Google Scholar
  10. J.-F. Couturier, R. Letourneur, and M. Liedloff. On the number of minimal dominating sets on some graph classes. Theoretical Computer Science, 562:634-642, 2015. Google Scholar
  11. N. Creignou, M. Kröll, R. Pichler, S. Skritek, and H. Vollmer. A complexity theory for hard enumeration problems. Discrete Applied Mathematics, 268:191-209, 2019. Google Scholar
  12. T. Eiter and G. Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278-1304, 1995. Google Scholar
  13. H. Fernau, P. A. Golovach, and M.-F. Sagot. Algorithmic enumeration: Output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421). Dagstuhl Reports, 8(10):63-86, 2018. Google Scholar
  14. F. V. Fomin, F. Grandoni, and D. Kratsch. Solving Connected Dominating Set faster than 2ⁿ. Algorithmica, 52:153-166, 2008. Google Scholar
  15. F. V. Fomin, F. Grandoni, and D. Kratsch. A measure & conquer approach for the analysis of exact algorithms. Journal of the ACM, 56(5), 2009. Google Scholar
  16. F. V. Fomin, F. Grandoni, A. V. Pyatkin, and A. A. Stepanov. Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Transactions on Algorithms, 5(1):1-17, 2008. Google Scholar
  17. F. V. Fomin and D. Kratsch. Exact Exponential Algorithms. Texts in Theoretical Computer Science. Springer, 2010. Google Scholar
  18. A. Gainer-Dewar and P. Vera-Licona. The minimal hitting set generation problem: Algorithms and computation. SIAM Journal of Discrete Mathematics, 31(1):63-100, 2017. Google Scholar
  19. P. A. Golovach, P. Heggernes, M. Moustapha Kanté, D. Kratsch, and Y. Villanger. Minimal dominating sets in interval graphs and trees. Discrete Applied Mathematics, 216:162-170, 2017. Google Scholar
  20. P. A. Golovach, P. Heggernes, and D. Kratsch. Enumerating minimal connected dominating sets in graphs of bounded chordality. Theoretical Computer Science, 630:63-75, 2016. Google Scholar
  21. P. A. Golovach, P. Heggernes, D. Kratsch, and R. Saei. Enumeration of minimal connected dominating sets for chordal graphs. Discrete Applied Mathematics, 278:3-11, 2020. Google Scholar
  22. T. W. Haynes, S. T. Hedetniemi, and P. J. Slater. Fundamentals of Domination in Graphs, volume 208 of Monographs and Textbooks in Pure and Applied Mathematics. Marcel Dekker, 1998. Google Scholar
  23. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  24. Y. Iwata. A faster algorithm for dominating set analyzed by the potential method. In D. Marx and P. Rossmanith, editors, Parameterized and Exact Computation - 6th International Symposium, IPEC 2011, volume 7112 of LNCS, pages 41-54. Springer, 2012. Google Scholar
  25. K. Kangas, P. Kaski, J. H. Korhonen, and M. Koivisto. On the number of connected sets in bounded degree graphs. Electron. J. Comb., 25(4):P4.34, 2018. Google Scholar
  26. M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM Journal of Discrete Mathematics, 28(4):1916-1929, 2014. Google Scholar
  27. E. L. Lawler. A note on the complexity of the chromatic number problem. Information Processing Letters, 5(3):66-67, 1976. Google Scholar
  28. D. Lokshtanov, D. Marx, and S. Saurabh. Lower bounds based on the Exponential Time Hypothesis. EATCS Bulletin, 105:41-72, 2011. Google Scholar
  29. D. Lokshtanov, M. Pilipczuk, and S. Saurabh. Below all subsets for minimal connected dominating set. SIAM Journal of Discrete Mathematics, 32(3):2332-2345, 2018. Google Scholar
  30. J. W. Moon and L. Moser. On cliques in graphs. Israel Journal of Mathematics, 3:23-28, 1965. Google Scholar
  31. J. Nederlof, J. M. M. van Rooij, and T. C. van Dijk. Inclusion/exclusion meets measure and conquer. Algorithmica, 69(3):685-740, 2014. Google Scholar
  32. M. Y. Sayadi. Construction et analyse des algorithmes exacts et exponentiels: énumération input-sensitive. (Design and analysis of exact exponential algorithms: input-sensitive enumeration). PhD thesis, University of Lorraine, Nancy, France, 2019. Google Scholar
  33. M. Y. Sayadi. On the maximum number of minimal connected dominating sets in convex bipartite graphs. Technical Report abs/1908.02174, Cornell University, ArXiv, 2019. URL: http://arxiv.org/abs/1908.02174.
  34. I. B. Skjørten. Faster enumeration of minimal connected dominating sets in split graphs. Master’s thesis, Department of Informatics, University of Bergen, Norway, June 2017. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact