Skip to main content
Log in

An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets

  • Published:
Algorithmica Aims and scope Submit manuscript

Abstract

We show that all minimal edge dominating sets of a graph can be generated in incremental polynomial time. We present an algorithm that solves the equivalent problem of enumerating minimal (vertex) dominating sets of line graphs in incremental polynomial, and consequently output polynomial, time. Enumeration of minimal dominating sets in graphs has recently been shown to be equivalent to enumeration of minimal transversals in hypergraphs. The question whether the minimal transversals of a hypergraph can be enumerated in output polynomial time is a fundamental and challenging question; it has been open for several decades and has triggered extensive research. To obtain our result, we present a flipping method to generate all minimal dominating sets of a graph. Its basic idea is to apply a flipping operation to a minimal dominating set \(D^*\) to generate minimal dominating sets \(D\) such that \(G[D]\) contains more edges than \(G[D^*]\). We show that the flipping method works efficiently on line graphs, resulting in an algorithm with delay \(O(n^2m^2|\mathcal {L}|)\) between each pair of consecutively output minimal dominating sets, where \(n\) and \(m\) are the numbers of vertices and edges of the input graph, respectively, and \(\mathcal {L}\) is the set of already generated minimal dominating sets. Furthermore, we are able to improve the delay to \(O(n^2m|\mathcal {L}|)\) on line graphs of bipartite graphs. Finally we show that the flipping method is also efficient on graphs of large girth, resulting in an incremental polynomial time algorithm to enumerate the minimal dominating sets of graphs of girth at least 7.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. We are grateful to the anonymous referee who pointed to us that an output polynomial time algorithm for graph of girth at least 5 can be derived from the results of Khachyan et al. [24] about hypergraphs with bounded edge-intersections.

  2. Note that \(N(v_j)\cap (N(v){\setminus } N[u])\) might be empty.

References

  1. Avis, D., Fukuda, K.: Reverse search for enumeration. Discret. Appl. Math. 65, 21–46 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  2. Beineke, L.W.: Characterizations of derived graphs. J. Comb. Theory 9, 129–135 (1970)

    Article  MATH  MathSciNet  Google Scholar 

  3. Boros, E., Elbassioni, K., Gurvich, V.: Transversal hypergraphs to perfect matchings in bipartite graphs: characterization and generation algorithms. J. Graph Theory 53, 209–232 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  4. Boros, E., Elbassioni, K., Gurvich, V., Khachiyan, L.: Generating maximal independent sets for hypergraphs with bounded edge-intersections. In: Proceedings of LATIN 2004. Lecture Notes in Computer Science, vol. 2976, pp. 488–498 (2004)

  5. Boros, E., Gurvich, V., Hammer, P.L.: Dual subimplicants of positive boolean functions. Optim. Methods Softw. 10, 147–156 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  6. Boros, E., Hammer, P.L., Ibaraki, T., Kawakami, K.: Polynomial time recognition of 2-monotonic positive Boolean functions given by an oracle. SIAM J. Comput. 26, 93–109 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  7. Courcelle, B.: Linear delay enumeration and monadic second-order logic. Discret. Appl. Math. 157, 2675–2700 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  8. Domingo, C., Mishra, N., Pitt, L.: Efficient read-restricted monotone cnf/dnf dualization by learning with membership queries. Mach. Learn. 37, 89–110 (1999)

    Article  MATH  Google Scholar 

  9. Eiter, T.: Exact transversal hypergraphs and application to Boolean \(\mu \)-functions. J. Symb. Comput. 17, 215–225 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  10. Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24, 1278–1304 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  11. Eiter, T., Gottlob, G.: Hypergraph transversal computation and related problems in Logic and AI. In: Proceedings of JELIA 2002. Lecture Notes in Computer Science, vol. 2424, pp. 549–564 (2002)

  12. Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput. 32, 514–537 (2003). Preliminary version in STOC 2002

    Article  MATH  MathSciNet  Google Scholar 

  13. Elbassioni, K., Makino, K., Rauf, I.: Output-sensitive algorithms for enumerating minimal transversals for some geometric hypergraphs. In: Proceedings of ESA 2009. Lecture Notes in Computer Science, vol. 5757, pp. 143–154 (2009)

  14. Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21, 618–628 (1996)

    Article  MATH  MathSciNet  Google Scholar 

  15. Golovach, P.A., Heggernes, P., Kratsch, D., Villanger, Y.: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. In: Proceedings of ICALP 2013. Lecture Notes in Computer Science, vol. 7965, pp. 485–496 (2013)

  16. Harary, F., Norman, R.Z.: Some properties of line digraphs. Rendi. del Circ. Mat. di Palermo 9, 161–169 (1960)

    Article  MATH  MathSciNet  Google Scholar 

  17. Haynes, T.W., Hedetniemi, S.T.: Domination in Graphs. Marcel Dekker, New York (1998)

    Google Scholar 

  18. Hemminger, R.L., Beineke, L.W.: Line graphs and line digraphs. In: Beineke, L.W., Wilson, R.J. (eds.) Selected Topics in Graph Theory, pp. 271–305. Academic Press, London (1978)

    Google Scholar 

  19. Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: On generating all maximal independent sets. Inf. Processing Lett. 27, 119–123 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  20. Kanté, M.M., Limouzy, V., Mary, A., Nourine, L.: Enumeration of minimal dominating sets and variants. In: Proceedings of FCT 2011. Lecture Notes in Computer Science, vol. 6914, pp. 298–394 (2011)

  21. Kanté, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. http://www.isima.fr/~/kante/research.php (in press)

  22. Kanté, M.M., Limouzy, V., Mary, A., Nourine, L.: On the neighbourhood Helly of some graph classes and applications to the enumeration of minimal dominating sets. In: Proceedings of ISAAC 2012. Lecture Notes in Computer Science, vol. 7676, pp. 289–298 (2012)

  23. Kanté, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: On the enumeration and counting of minimal dominating sets in interval and permutation graphs. In: Proceedings of ISAAC 2013. Lecture Notes in Computer Science, vol. 8283, pp. 329–339 (2013)

  24. Khachiyan, L., Boros, E., Borys, K., Elbassioni, K.M., Gurvich, V.: On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. Theor. Comput. Sci. 382, 139–150 (2007)

    Article  MATH  Google Scholar 

  25. Khachiyan, L., Boros, E., Borys, K., Elbassioni, K.M., Gurvich, V.: Generating all vertices of a polyhedron is hard. Discret. Comput. Geom. 39, 174–190 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  26. Khachiyan, L., Boros, L., Borys, K., Elbassioni, K.M., Gurvich, V., Makino, K.: Generating cut conjunctions in graphs and related problems. Algorithmica 51, 239–263 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  27. Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: On enumerating minimal dicuts and strongly connected subgraphs. Algorithmica 50, 159–172 (2008)

    Article  MathSciNet  Google Scholar 

  28. Krausz, J.: Démonstration nouvelle d’un théorème de Whitney sur les réseaux. Mat. Fiz. Lapok 50, 75–85 (1943)

    MATH  MathSciNet  Google Scholar 

  29. Lawler, E.L., Lenstra, J.K.: Generating all maximal independent sets: NP-hardness and polynomial-time algorithms. SIAM J. Comput. 9, 558–565 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  30. Makino, K., Ibaraki, T.: The maximum latency and identification of positive Boolean functions. SIAM J. Comput. 26, 1363–1383 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  31. Makino, K., Ibaraki, T.: A fast and simple algorithm for identifying 2-monotonic positive Boolean functions. J. Algorithms 26, 293–305 (1998)

    Article  MathSciNet  Google Scholar 

  32. Papadimitriou, C.: NP-completeness: a retrospective. In: Proceedings of ICALP 1997. Lecture Notes in Computer Science, vol. 1256, pp. 2–6 (1997)

  33. Roussopoulos, N.D.: A max \(\{m, n\}\) algorithm for determining the graph \(H\) from its line graph \(G\). Inf. Process. Lett. 2, 108–112 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  34. Schwikowski, B., Speckenmeyer, E.: On enumerating all minimal solutions of feedback problems. Discret. Appl. Math. 117, 253–265 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  35. Tarjan, R.E.: Enumeration of the elementary circuits of a directed graph. SIAM J. Comput. 2, 211–216 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  36. Tsukiyama, S., Ide, M., Ariyoshi, H., Shirakawa, I.: A new algorithm for generating all the maximal independent sets. SIAM J. Comput. 6, 505–517 (1977)

    Article  MATH  MathSciNet  Google Scholar 

  37. Tsukiyama, S., Shirakawa, I., Ozaki, H., Ariyoshi, H.: An algorithm to enumerate all cutsets of a graph in linear time per cutset. J. ACM 27, 619–632 (1980)

    Article  MATH  MathSciNet  Google Scholar 

  38. Whitney, H.: Congruent graphs and the connectivity of graphs. Am. J. Math. 54, 150–168 (1932)

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgments

The research leading to these results has received funding from the Research Council of Norway, the French National Research Agency, and the European Research Council under the European Union’s Seventh Framework Programme (FP/2007–2013) / ERC Grant Agreement No. 267959. A preliminary extended abstract appeared at ICALP 2013 [15].

Author information

Authors and Affiliations

Authors

Corresponding author

Correspondence to Petr A. Golovach.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Golovach, P.A., Heggernes, P., Kratsch, D. et al. An Incremental Polynomial Time Algorithm to Enumerate All Minimal Edge Dominating Sets. Algorithmica 72, 836–859 (2015). https://doi.org/10.1007/s00453-014-9875-7

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00453-014-9875-7

Keywords

Navigation