Nothing Special   »   [go: up one dir, main page]
Document Open Access Logo

Efficient Enumeration of Dominating Sets for Sparse Graphs

Authors Kazuhiro Kurita, Kunihiro Wasa , Hiroki Arimura, Takeaki Uno

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2018.8.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Kazuhiro Kurita
  • IST, Hokkaido University, Sapporo, Japan
Kunihiro Wasa
  • National Institute of Informatics, Tokyo, Japan
Hiroki Arimura
  • IST, Hokkaido University, Sapporo, Japan
Takeaki Uno
  • National Institute of Informatics, Tokyo, Japan

Cite AsGet BibTex

Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient Enumeration of Dominating Sets for Sparse Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ISAAC.2018.8

Abstract

A dominating set D of a graph G is a set of vertices such that any vertex in G is in D or its neighbor is in D. Enumeration of minimal dominating sets in a graph is one of central problems in enumeration study since enumeration of minimal dominating sets corresponds to enumeration of minimal hypergraph transversal. However, enumeration of dominating sets including non-minimal ones has not been received much attention. In this paper, we address enumeration problems for dominating sets from sparse graphs which are degenerate graphs and graphs with large girth, and we propose two algorithms for solving the problems. The first algorithm enumerates all the dominating sets for a k-degenerate graph in O(k) time per solution using O(n + m) space, where n and m are respectively the number of vertices and edges in an input graph. That is, the algorithm is optimal for graphs with constant degeneracy such as trees, planar graphs, H-minor free graphs with some fixed H. The second algorithm enumerates all the dominating sets in constant time per solution for input graphs with girth at least nine.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Enumeration algorithm
  • polynomial amortized time
  • dominating set
  • girth
  • degeneracy

Metrics

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

References

  1. David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Appl. Math., 65(1):21-46, 1996. Google Scholar
  2. Etienne Birmelé, Rui A. Ferreira, Roberto Grossi, Andrea Marino, Nadia Pisanti, Romeo Rizzi, and Gustavo Sacomoto. Optimal Listing of Cycles and st-Paths in Undirected Graphs. In Proc. SODA 2013 ACM, pages 1884-1896, 2013. Google Scholar
  3. Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Leonid Khachiyan. Generating maximal independent sets for hypergraphs with bounded edge-intersections. In Proc. LATIN 2004, pages 488-498. Springer, 2004. Google Scholar
  4. Boštjan Brešar, Michael A Henning, and Douglas F Rall. RAINBOW DOMINATION IN GRAPHS. Taiwanese J. Math., 12(1):213-225, 2008. Google Scholar
  5. L Sunil Chandran and CR Subramanian. Girth and treewidth. J. Combin. Theory Ser. B, 93(1):23-32, 2005. Google Scholar
  6. Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari. Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques. In Proc. ICALP 2016, volume 55 of LIPIcs, pages 148:1-148:15. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.148.
  7. Bruno Courcelle. Linear delay enumeration and monadic second-order logic. Discrete Appl. Math., 157(12):2675-2700, 2009. Google Scholar
  8. Nadia Creignou, Markus Kröll, Reinhard Pichler, Sebastian Skritek, and Heribert Vollmer. On the Complexity of Hard Enumeration Problems. In Proc. LATA 2017, volume 10168 of LNCS, pages 183-195. Springer, 2017. Google Scholar
  9. Jean-Alexandre Anglès d’Auriac, Csilia Bujtás, Hakim El Maftouhi, Marek Karpinski, Yannis Manoussakis, Leandro Montero, Narayanan Narayanan, Laurent Rosaz, Johan Thapper, and Zsolt Tuza. Tropical Dominating Sets in Vertex-Coloured Graphs. In Proc. WALCOM 2016, pages 17-27. Springer, 2016. Google Scholar
  10. Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. New Results on Monotone Dualization and Generating Hypergraph Transversals. SIAM J. Comput., 32(2):514-537, 2003. URL: http://dx.doi.org/10.1137/S009753970240639X.
  11. David Eppstein, Maarten Löffler, and Darren Strash. Listing All Maximal Cliques in Large Sparse Real-World Graphs. J. Exp. Algorithmics, 18:3.1:3.1-3.1:3.21, November 2013. URL: http://dx.doi.org/10.1145/2543629.
  12. Michael R. Garey and David S. Johnson. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman &Co., New York, NY, USA, 1990. Google Scholar
  13. Petr A Golovach, Pinar Heggernes, Mamadou M Kanté, Dieter Kratsch, and Yngve Villanger. Enumerating minimal dominating sets in chordal bipartite graphs. Discrete Appl. Math., 199(30):30-36, 2016. Google Scholar
  14. Petr A Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve H Sæther, and Yngve Villanger. Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. Algorithmica, 80(2):714-741, 2018. Google Scholar
  15. Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, and Yngve Villanger. An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. Algorithmica, 72(3):836-859, 2015. URL: http://dx.doi.org/10.1007/s00453-014-9875-7.
  16. Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. Enumeration of Minimal Dominating Sets and Variants. In Proc. FCT 2011, pages 298-309. Springer, 2011. Google Scholar
  17. Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. On the Neighbourhood Helly of Some Graph Classes and Applications to the Enumeration of Minimal Dominating Sets. In Proc. ISAAC 2012, volume 7676, pages 289-298. Springer, 2012. Google Scholar
  18. Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. On the Enumeration of Minimal Dominating Sets and Related Notions. SIAM J. Discrete Math., 28(4):1916-1929, 2014. Google Scholar
  19. Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In Proc. WG 2015, pages 138-153. Springer, 2015. Google Scholar
  20. Mamadou Moustapha Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. Polynomial Delay Algorithm for Listing Minimal Edge Dominating Sets in Graphs. In Proc. WADS 2015, volume 9214 of LNCS, pages 446-457. Springer Berlin Heidelberg, 2015. Google Scholar
  21. E. L. Lawler, J. K. Lenstra, and A. H. G. Rinnooy Kan. Generating All Maximal Independent Sets: NP-Hardness and Polynomial-Time Algorithms. SIAM J. Comput., 9(3):558-565, 1980. URL: http://dx.doi.org/10.1137/0209042.
  22. Don R Lick and Arthur T White. k-DEGENERATE GRAPHS. Canadian J. Math., 22:1082-1096, 1970. Google Scholar
  23. Kazuhisa Makino and Takeaki Uno. New Algorithms for Enumerating All Maximal Cliques. In Proc. SWAT 2004, volume 3111 of LNCS, pages 260-272. Springer, 2004. Google Scholar
  24. David W Matula and Leland L Beck. Smallest-last ordering and clustering and graph coloring algorithms. J. ACM, 30(3):417-427, 1983. Google Scholar
  25. Akiyoshi Shioura, Akihisa Tamura, and Takeaki Uno. An Optimal Algorithm for Scanning All Spanning Trees of Undirected Graphs. SIAM J. Comput., 26(3):678-692, 1997. Google Scholar
  26. Andrew Thomason. The Extremal Function for Complete Minors. Journal of Combinatorial Theory, Series B, 81(2):318-338, 2001. Google Scholar
  27. Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient Enumeration of Induced Subtrees in a K-Degenerate Graph. In Proc. ISAAC 2014, volume 8889 of LNCS, pages 94-102. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-319-13075-0_8.
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 Imprint Privacy Contact