Document Open Access Logo

Enumerating Minimal Transversals of Hypergraphs without Small Holes

Authors Mamadou M. Kanté, Kaveh Khoshkhah, Mozhgan Pourmoradnasseri

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2018.55.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Author Details

Mamadou M. Kanté
  • Université Clermont Auvergne, LIMOS, CNRS , Aubiére, France
Kaveh Khoshkhah
  • Institute of Computer Science, University of Tartu , Tartu, Estonia
Mozhgan Pourmoradnasseri
  • Université Clermont Auvergne, LIMOS, CNRS , Aubiére, France

Funding

M. M. Kanté and M. Pourmoradnasseri are supported by the French Agency for Research under the GraphEN project ANR-15-CE40-0009.
  • Khoshkhah, Kaveh: Kaveh Khoshkhah was supported by the Estonian Research Council, ETAG (Eesti Teadusagentuur), through PUT Exploratory Grant #620.

Cite AsGet BibTex

Mamadou M. Kanté, Kaveh Khoshkhah, and Mozhgan Pourmoradnasseri. Enumerating Minimal Transversals of Hypergraphs without Small Holes. In 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 117, pp. 55:1-55:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.MFCS.2018.55

Abstract

We give a polynomial delay algorithm for enumerating the minimal transversals of hypergraphs without induced cycles of length 3 and 4. As a corollary, we can enumerate, with polynomial delay, the vertices of any polyhedron P(A,1)={x in R^n | Ax >= 1, x >= 0}, when A is a balanced matrix that does not contain as a submatrix the incidence matrix of a cycle of length 4. Other consequences are a polynomial delay algorithm for enumerating the minimal dominating sets of graphs of girth at least 9 and an incremental delay algorithm for enumerating all the minimal dominating sets of a bipartite graph without induced 6 and 8-cycles.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph enumeration
  • Mathematics of computing → Graph algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • Triangle-free Hypergraph
  • Minimal Transversal
  • Balanced Matrix
  • Minimal Dominating Set

Metrics

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

References

  1. MHG Anthony and Norman Biggs. Computational learning theory, volume 30. Cambridge University Press, 1997. Google Scholar
  2. David Avis and Komei Fukuda. Reverse search for enumeration. Discrete Appl. Math., 65(1-3):21-46, 1996. First International Colloquium on Graphs and Optimization (GOI), 1992 (Grimentz). URL: http://dx.doi.org/10.1016/0166-218X(95)00026-N.
  3. James Bailey, Thomas Manoukian, and Kotagiri Ramamohanarao. A fast algorithm for computing hypergraph transversals and its application in mining emerging patterns. In Data Mining, 2003. ICDM 2003. Third IEEE International Conference on, pages 485-488. IEEE, 2003. Google Scholar
  4. Claude Berge. Hypergraphs: combinatorics of finite sets, volume 45. Elsevier, 1984. Google Scholar
  5. Endre Boros, Khaled Elbassioni, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino. Dual-bounded generating problems: All minimal integer solutions for a monotone system of linear inequalities. SIAM Journal on Computing, 31(5):1624-1643, 2002. Google Scholar
  6. Endre Boros, Khaled Elbassioni, Vladimir Gurvich, and Hans Raj Tiwary. The negative cycles polyhedron and hardness of checking some polyhedral properties. Annals of Operations Research, 188(1):63-76, 2011. Google Scholar
  7. Endre Boros, Vladimir Gurvich, and Peter L. Hammer. Dual subimplicants of positive Boolean functions. Optim. Methods Softw., 10(2):147-156, 1998. Dedicated to Professor Masao Iri on the occasion of his 65th birthday. URL: http://dx.doi.org/10.1080/10556789808805708.
  8. Endre Boros, Vladimir Gurvich, Leonid Khachiyan, and Kazuhisa Makino. On the complexity of generating maximal frequent and minimal infrequent sets. In Annual Symposium on Theoretical Aspects of Computer Science, pages 133-141. Springer, 2002. Google Scholar
  9. Michael R Bussieck and Marco E Lübbecke. The vertex set of a 0/1-polytope is strongly p-enumerable. Computational Geometry, 11(2):103-109, 1998. Google Scholar
  10. Michele Conforti, Gérard Cornuéjols, and MR Rao. Decomposition of balanced matrices. Journal of Combinatorial Theory, Series B, 77(2):292-406, 1999. Google Scholar
  11. T. Eiter, G. Gottlob, and K. 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.
  12. Thomas Eiter and Georg Gottlob. Identifying the minimal transversals of a hypergraph and related problems. SIAM Journal on Computing, 24(6):1278-1304, 1995. Google Scholar
  13. Khaled Elbassioni and Kazuhisa Makino. Enumerating Vertices of 0/1-Polyhedra associated with 0/1-Totally Unimodular Matrices. In David Eppstein, editor, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018), volume 101 of Leibniz International Proceedings in Informatics (LIPIcs), pages 18:1-18:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.SWAT.2018.18.
  14. Michael L Fredman and Leonid Khachiyan. On the complexity of dualization of monotone disjunctive normal forms. Journal of Algorithms, 21(3):618-628, 1996. Google Scholar
  15. Komei Fukuda. Lecture: polyhedral computation. Technical report, Research Report, Department of Mathematics, and Institute of Theoretical Computer Science ETH Zurich, available online, 2004. Google Scholar
  16. Petr A. Golovach, Pinar Heggernes, Mamadou Moustapha Kanté, Dieter Kratsch, Sigve Hortemo Sæther, and Yngve Villanger. Output-polynomial enumeration on graphs of bounded (local) linear mim-width. Algorithmica, 80(2):714-741, 2018. URL: http://dx.doi.org/10.1007/s00453-017-0289-1.
  17. 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. Google Scholar
  18. Dimitrios Gunopulos, Heikki Mannila, Roni Khardon, and Hannu Toivonen. Data mining, hypergraph transversals, and machine learning. In Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, pages 209-216. ACM, 1997. Google Scholar
  19. VA Gurvich. On theory of multistep games. USSR Computational Mathematics and Mathematical Physics, 13(6):143-161, 1973. Google Scholar
  20. M. M. Kanté, V. Limouzy, A. Mary, and L. Nourine. On the enumeration of minimal dominating sets and related notions. SIAM J. Discrete Math., 28(4):1916-1929, 2014. URL: http://dx.doi.org/10.1137/120862612.
  21. Dimitris J. Kavvadias and Elias C. Stavropoulos. An efficient algorithm for the transversal hypergraph generation. J. Graph Algorithms Appl., 9(2):239-264 (electronic), 2005. URL: http://dx.doi.org/10.7155/jgaa.00107.
  22. L. Khachiyan, E. Boros, K. Borys, K. M. Elbassioni, V. Gurvich, and K. Makino. Generating cut conjunctions in graphs and related problems. Algorithmica, 51(3):239-263, 2008. URL: http://dx.doi.org/10.1007/s00453-007-9111-9.
  23. Leonid Khachiyan, Endre Boros, Konrad Borys, Vladimir Gurvich, and Khaled Elbassioni. Generating all vertices of a polyhedron is hard. In Twentieth Anniversary Volume:, pages 1-17. Springer, 2009. Google Scholar
  24. Leonid Khachiyan, Endre Boros, Khaled Elbassioni, and Vladimir Gurvich. An efficient implementation of a quasi-polynomial algorithm for generating hypergraph transversals and its application in joint generation. Discrete Applied Mathematics, 154(16):2350-2372, 2006. Google Scholar
  25. Leonid Khachiyan, Endre Boros, Khaled M. Elbassioni, and Vladimir Gurvich. On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. Theor. Comput. Sci., 382(2):139-150, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.03.005.
  26. Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, and Takeaki Uno. Efficient enumeration of dominating sets for sparse graphs. arXiv preprint arXiv:1802.07863, 2018. Google Scholar
  27. Alfred Lehman. On the width-length inequality. Mathematical Programming, 16(1):245-259, 1979. Google Scholar
  28. Kazuhisa Makino and Takeaki Uno. New algorithms for enumerating all maximal cliques. In Torben Hagerup and Jyrki Katajainen, editors, Algorithm Theory - SWAT 2004, 9th Scandinavian Workshop on Algorithm Theory, Humlebaek, Denmark, July 8-10, 2004, Proceedings, volume 3111 of Lecture Notes in Computer Science, pages 260-272. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-27810-8_23.
  29. Ronald C Read. Every one a winner or how to avoid isomorphism search when cataloguing combinatorial configurations. In Annals of Discrete Mathematics, volume 2, pages 107-120. Elsevier, 1978. Google Scholar
  30. Alexander Schrijver. Theory of linear and integer programming. John Wiley &Sons, 1998. Google Scholar
  31. Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pages 488-495, 2009. Google Scholar
  32. Kunihiro Wasa. Enumeration of enumeration algorithms. arXiv preprint arXiv:1605.05102, 2016. 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 Imprint Privacy Contact