research-article

Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants

Authors:

Michał Pilipczuk,

Jean-Florent RaymondAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 16, Issue 3

Article No.: 39, Pages 1 - 23

https://doi.org/10.1145/3386686

Published: 06 June 2020 Publication History

Abstract

It is a long-standing open problem whether the minimal dominating sets of a graph can be enumerated in output-polynomial time. In this article we investigate this problem in graph classes defined by forbidding an induced subgraph. In particular, we provide output-polynomial time algorithms for K_t-free graphs and for several related graph classes. This answers a question of Kanté et al. about enumeration in bipartite graphs.

References

[1]

Eralp Abdurrahim Akkoyunlu. 1973. The enumeration of maximal cliques of large graphs. SIAM J. Comput. 2, 1 (1973), 1--6.

Digital Library

[2]

John M. Barnard. 1993. Substructure searching methods: Old and new. J. Chem. Inf. Comput. Sci. 33, 4 (1993), 532--538.

[3]

Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. 2019. Enumerating minimal dominating sets in triangle-free graphs. In Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[4]

Bruno Courcelle. 2009. Linear delay enumeration and monadic second-order logic. Discr. Appl. Math. 157, 12 (2009), 2675--2700.

Digital Library

[5]

Jean-François Couturier, Pinar Heggernes, Pim van’t Hof, and Dieter Kratsch. 2013. Minimal dominating sets in graph classes: Combinatorial bounds and enumeration. Theor. Comput. Sci. 487 (2013), 82--94.

[6]

Peter Damaschke. 2006. Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351, 3 (2006), 337--350.

Digital Library

[7]

Thomas Eiter and Georg Gottlob. 2002. Hypergraph transversal computation and related problems in logic and AI. In Proceedings of the European Workshop on Logics in Artificial Intelligence. Springer, 549--564.

[8]

Thomas Eiter, Georg Gottlob, and Kazuhisa Makino. 2003. New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput. 32, 2 (2003), 514--537.

Digital Library

[9]

Thomas Eiter, Kazuhisa Makino, and Georg Gottlob. 2008. Computational aspects of monotone dualization: A brief survey. Discr. Appl. Math. 156, 11 (2008), 2035--2049.

Digital Library

[10]

Henning Fernau, Petr A. Golovach, and Marie-France Sagot. 2019. Algorithmic enumeration: Output-sensitive, input-sensitive, parameterized, approximative (Dagstuhl Seminar 18421). Dagstuhl Rep. 8, 10 (2019), 63--86.

[11]

Fedor V. Fomin, Fabrizio Grandoni, Artem V. Pyatkin, and Alexey A. Stepanov. 2008. Combinatorial bounds via measure and conquer: Bounding minimal dominating sets and applications. ACM Trans. Algor. 5, 1 (2008), 9.

Digital Library

[12]

Michael L. Fredman and Leonid Khachiyan. 1996. On the complexity of dualization of monotone disjunctive normal forms. J. Algor. 21, 3 (1996), 618--628.

Digital Library

[13]

Komei Fukuda, Thomas M. Liebling, and François Margot. 1997. Analysis of backtrack algorithms for listing all vertices and all faces of a convex polyhedron. Comput. Geom. 8, 1 (1997), 1--12.

Digital Library

[14]

Petr A. Golovach, Pinar Heggernes, Mamadou M. Kanté, Dieter Kratsch, Sigve H. Sæther, and Yngve Villanger. 2018. Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Algorithmica 80, 2 (2018), 714--741.

Digital Library

[15]

Petr A. Golovach, Pinar Heggernes, Mamadou M. Kanté, Dieter Kratsch, and Yngve Villanger. 2016. Enumerating minimal dominating sets in chordal bipartite graphs. Discr. Appl. Math. 199 (2016), 30--36.

Digital Library

[16]

Petr A. Golovach, Pinar Heggernes, Dieter Kratsch, and Yngve Villanger. 2015. An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica 72, 3 (2015), 836--859.

Digital Library

[17]

Petr A. Golovach, Dieter Kratsch, Mathieu Liedloff, and Mohamed Yosri Sayadi. 2019. Enumeration and maximum number of minimal dominating sets for chordal graphs. Theor. Comput. Sci. 783 (2019), 41--52.

Digital Library

[18]

Joshua A. Grochow and Manolis Kellis. 2007. Network motif discovery using subgraph enumeration and symmetry-breaking. In Proceedings of the Annual International Conference on Research in Computational Molecular Biology. Springer, 92--106.

[19]

David S. Johnson, Mihalis Yannakakis, and Christos H. Papadimitriou. 1988. On generating all maximal independent sets. Inf. Process. Lett. 27, 3 (1988), 119--123.

Digital Library

[20]

Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. 2011. Enumeration of minimal dominating sets and variants. In Proceedings of the International Symposium on Fundamentals of Computation Theory. Springer, 298--309.

[21]

Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. 2012. On the neighbourhood helly of some graph classes and applications to the enumeration of minimal dominating sets. In Proceedings of the International Symposium on Algorithms and Computation. Springer, 289--298.

[22]

Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, and Lhouari Nourine. 2014. On the enumeration of minimal dominating sets and related notions. SIAM J. Discr. Math. 28, 4 (2014), 1916--1929.

[23]

Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. 2013. On the enumeration and counting of minimal dominating sets in interval and permutation graphs. In Proceedings of the International Symposium on Algorithms and Computation. Springer, 339--349.

[24]

Mamadou M. Kanté, Vincent Limouzy, Arnaud Mary, Lhouari Nourine, and Takeaki Uno. 2015. A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In Proceedings of the International Workshop on Graph-Theoretic Concepts in Computer Science. Springer, 138--153.

[25]

Mamadou M. Kanté and Lhouari Nourine. 2016. Minimal dominating set enumeration. In Encyclopedia of Algorithms, Ming-Yang Kao (Ed.). Springer US, Boston, MA, 1287--1291.

[26]

Mitchell P. Marcus. 1964. Derivation of maximal compatibles using Boolean algebra. IBM J. Res. Dev. 8, 5 (1964), 537--538.

Digital Library

[27]

Andrea Marino. 2015. Analysis and Enumeration: Algorithms for Biological Graphs. Vol. 6. Springer.

[28]

Marvin C. Paull and Stephen H. Unger. 1959. Minimizing the number of states in incompletely specified sequential switching functions. IRE Trans. Electr. Comput. EC-8, 3 (1959), 356--367.

[29]

Jean-Florent Raymond. 2019. minimal_dominating_sets, an Implementation of Bonamy et al.’s Algorithm for Enumerating Minimal Dominating Sets in -free Graphs. Retrieved February 25, 2020 https://git.sagemath.org/sage.git/commit?id=906cf147fe64ceed73d30fabf61155f65393bd67.

[30]

Ronald C. Read and Robert E. Tarjan. 1975. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5, 3 (1975), 237--252.

Digital Library

[31]

Yann Strozecki. 2019. Enumeration complexity. Bull. EATCS 1, 129 (2019).

[32]

Yann Strozecki and Arnaud Mary. 2019. Efficient enumeration of solutions produced by closure operations. Discr. Math. Theor. Comput. Sci. 21, 3 (2019).

[33]

Robert E. Tarjan. 1973. Enumeration of the elementary circuits of a directed graph. SIAM J. Comput. 2, 3 (1973), 211--216.

Digital Library

[34]

James C. Tiernan. 1970. An efficient search algorithm to find the elementary circuits of a graph. Commun. ACM 13, 12 (1970), 722--726.

Digital Library

[35]

Shuji Tsukiyama, Mikio Ide, Hiromu Ariyoshi, and Isao Shirakawa. 1977. A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 3 (1977), 505--517.

Digital Library

[36]

Kunihiro Wasa. 2016. Enumeration of enumeration algorithms. arxiv:1605.05102 (2016).

[37]

Xifeng Yan, Philip S. Yu, and Jiawei Han. 2005. Substructure similarity search in graph databases. In Proceedings of the 2005 ACM SIGMOD International Conference on Management of Data. ACM, 766--777.

Digital Library

Cited By

Kobayashi YKurita KMann KMatsui YOno H(2025)Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity ConstraintsAlgorithms10.3390/a1802011218:2(112)Online publication date: 17-Feb-2025
https://doi.org/10.3390/a18020112
Bergougnoux BDefrain OMc Inerney F(2025)Enumerating Minimal Solution Sets for Metric Graph ProblemsAlgorithmica10.1007/s00453-025-01300-4Online publication date: 25-Feb-2025
https://doi.org/10.1007/s00453-025-01300-4
Kurita KWasa K(2024)An approximation algorithm for K-best enumeration of minimal connected edge dominating sets with cardinality constraintsTheoretical Computer Science10.1016/j.tcs.2024.1146281005(114628)Online publication date: Jul-2024
https://doi.org/10.1016/j.tcs.2024.114628
Show More Cited By

Index Terms

Enumerating Minimal Dominating Sets in Kt-free Graphs and Variants
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Graph enumeration

Recommendations

Enumerating minimal dominating sets in chordal graphs

A structural theorem about the distribution of simplicial vertices in a chordal graph.An algorithm for enumerating minimal dominating sets in a chordal graph.Upper bound on number of minimal dominating sets improved from 1.6181 n to 1.5214 n . The ...
Enumerating minimal connected dominating sets in graphs of bounded chordality

Enumerating objects of specified type is one of the principal tasks in algorithmics. In graph algorithms one often enumerates vertex subsets satisfying a certain property. We study the enumeration of all minimal connected dominating sets of an input ...
On Dominating Graph of Graphs, Median Graphs, Partial Cubes and Complement of Minimal Dominating Sets
Abstract
The dominating graph of a graph G is a graph whose vertices correspond to the dominating sets of G and two vertices are adjacent whenever their corresponding dominating sets differ in exactly one vertex. Studying properties of dominating graph has ... $_{}$

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 16, Issue 3

July 2020

368 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/3403658

Editor:
Aravind Srinivasan
University of Maryland, USA

Issue’s Table of Contents

Copyright © 2020 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 June 2020

Online AM: 07 May 2020

Accepted: 01 March 2020

Revised: 01 February 2020

Received: 01 September 2019

Published in TALG Volume 16, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

ANR
European Union’s Horizon 2020 research and innovation programme
ERC consolidator

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)1

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Kobayashi YKurita KMann KMatsui YOno H(2025)Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity ConstraintsAlgorithms10.3390/a1802011218:2(112)Online publication date: 17-Feb-2025
https://doi.org/10.3390/a18020112
Bergougnoux BDefrain OMc Inerney F(2025)Enumerating Minimal Solution Sets for Metric Graph ProblemsAlgorithmica10.1007/s00453-025-01300-4Online publication date: 25-Feb-2025
https://doi.org/10.1007/s00453-025-01300-4
Kurita KWasa K(2024)An approximation algorithm for K-best enumeration of minimal connected edge dominating sets with cardinality constraintsTheoretical Computer Science10.1016/j.tcs.2024.1146281005(114628)Online publication date: Jul-2024
https://doi.org/10.1016/j.tcs.2024.114628
Abu-Khzam FFernau HMann K(2024)Minimal Roman Dominating Functions: Extensions and EnumerationAlgorithmica10.1007/s00453-024-01211-w86:6(1862-1887)Online publication date: 14-Feb-2024
https://doi.org/10.1007/s00453-024-01211-w
Bergougnoux BDefrain OMc Inerney F(2024)Enumerating Minimal Solution Sets for Metric Graph ProblemsGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-75409-8_4(50-64)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1007/978-3-031-75409-8_4
Bartier VDefrain OMc Inerney F(2024)Hypergraph Dualization with $$\textsf{FPT}$$-delay Parameterized by the Degeneracy and DimensionCombinatorial Algorithms10.1007/978-3-031-63021-7_9(111-125)Online publication date: 22-Jun-2024
https://doi.org/10.1007/978-3-031-63021-7_9
Kobayashi YKurita KMatsui YOno H(2024)Enumerating Minimal Vertex Covers and Dominating Sets with Capacity and/or Connectivity ConstraintsCombinatorial Algorithms10.1007/978-3-031-63021-7_18(232-246)Online publication date: 22-Jun-2024
https://doi.org/10.1007/978-3-031-63021-7_18
Abu-Khzam FFernau HMann K(2022)Minimal Roman Dominating Functions: Extensions and EnumerationGraph-Theoretic Concepts in Computer Science10.1007/978-3-031-15914-5_1(1-15)Online publication date: 1-Oct-2022
https://doi.org/10.1007/978-3-031-15914-5_1
Defrain ONourine LVilmin S(2021)Translating between the representations of a ranked convex geometryDiscrete Mathematics10.1016/j.disc.2021.112399344:7(112399)Online publication date: Jul-2021
https://doi.org/10.1016/j.disc.2021.112399
Kurita KWasa KArimura HUno T(2021)Efficient enumeration of dominating sets for sparse graphsDiscrete Applied Mathematics10.1016/j.dam.2021.06.004Online publication date: Jun-2021
https://doi.org/10.1016/j.dam.2021.06.004
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

HTML Format

View this article in HTML Format.

Figures

Tables

Media

View Issue’s Table of Contents