Abstract
A transversal of a hypergraph is a set of vertices intersecting each hyperedge. We design and analyze new exponential-time polynomial-space algorithms to enumerate all inclusion-minimal transversals of a hypergraph. For each fixed \(k\ge 3\), our algorithms for hypergraphs of rank k, where the rank is the maximum size of a hyperedge, outperform the previous best. This also implies improved upper bounds on the maximum number of minimal transversals in n-vertex hypergraphs of rank \(k\ge 3\). Our main algorithm is a branching algorithm whose running time is analyzed with Measure and Conquer. It enumerates all minimal transversals of hypergraphs of rank 3 in time \(O(1.6755^n)\). Our enumeration algorithms improve upon the best known algorithms for counting minimum transversals in hypergraphs of rank k for \(k\ge 3\) and for computing a minimum transversal in hypergraphs of rank k for \(k\ge 6\).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Cochefert, M., Couturier, J.-F., Gaspers, S., Kratsch, D.: Faster algorithms to enumerate hypergraph transversals. Technical report arxiv:1510.05093 (2015)
Couturier, J.-F., Heggernes, P., van ’t Hof, P., Kratsch, D.: Minimal dominating sets in graph classes: combinatorial bounds and enumeration. Theor. Comput. Sci. 487(8), 2–94 (2013)
Cygan, M., Dell, H., Lokshtanov, D., Marx, D., Nederlof, J., Okamoto, Y., Paturi, R., Saurabh, S., Wahlström, M.: On problems as hard as CNF–SAT. In: Proceedings of CCC, pp. 74–84 (2012)
Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24(6), 1278–1304 (1995)
Eiter, T., Gottlob, G., Makino, K.: New results on monotone dualization and generating hypergraph transversals. SIAM J. Comput. 32(2), 514–537 (2003)
Elbassioni, K.M., Rauf, I.: Polynomial-time dualization of r-exact hypergraphs with applications in geometry. Discrete Math. 310(17–18), 2356–2363 (2010)
Fernau, H.: Parameterized algorithmics for d-hitting set. Int. J. Comput. Math. 87(14), 3157–3174 (2010)
Fernau, H.: Parameterized algorithms for d-hitting set: the weighted case. Theor. Comput. Sci. 411(16–18), 1698–1713 (2010)
Fernau, H.: A top-down approach to search-trees: Improved algorithmics for 3-hitting set. Algorithmica 57(1), 97–118 (2010)
Fomin, F.V., Gaspers, S., Kratsch, D., Liedloff, M., Saurabh, S.: Iterative compression and exact algorithms. Theor. Comput. Sci. 411(7–9), 1045–1053 (2010)
Fomin, F.V., Gaspers, S., Lokshtanov, D., Saurabh, S.: Exact algorithms via monotone local search. Technical report arxiv:1512.01621 (2015)
Fomin, F.V., Kratsch, D.: Exact Exponential Algorithms. Springer, Heidelberg (2010)
Fredman, M.L., Khachiyan, L.: On the complexity of dualization of monotone disjunctive normal forms. J. Algorithms 21(3), 618–628 (1996)
Gaspers, S.: Algorithmes exponentiels. Master’s thesis, University Metz, France (2005)
Gaspers, S., Algorithms, E.T.: Exponential Time Algorithms: Structures, Measures, and Bounds. VDM Verlag Dr. Mueller e.K, Saarbrücken (2010)
Gaspers, S., Sorkin, G.B.: A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. J. Comput. Syst. Sci. 78(1), 305–335 (2012)
Golovach, P.A., Heggernes, P., Kratsch, D., Villanger, Y.: An incremental polynomial time algorithm to enumerate all minimal edge dominating sets. Algorithmica 72(3), 836–859 (2015)
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L.: On the enumeration of minimal dominating sets and related notions. SIAM J. Discrete Math. 28(4), 1916–1929 (2014)
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: A polynomial delay algorithm for enumerating minimal dominating sets in chordal graphs. In: Proceedings of WG (2015)
Kanté, M.M., Limouzy, V., Mary, A., Nourine, L., Uno, T.: Polynomial delay algorithm for listing minimal edge dominating sets in graphs. In: Dehne, F., Sack, J.-R., Stege, U. (eds.) WADS 2015. LNCS, vol. 9214, pp. 446–457. Springer, Heidelberg (2015)
Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W., Bohlinger, J.D. (eds.) Complexity of computer computations, pp. 85–103. Plenum Press, New York (1972)
Kavvadias, D.J., Stavropoulos, E.C.: An efficient algorithm for the transversal hypergraph generation. J. Graph Algorithms Appl. 9(2), 239–264 (2005)
Khachiyan, L., Boros, E., Elbassioni, K.M., Gurvich, V.: On the dualization of hypergraphs with bounded edge-intersections and other related classes of hypergraphs. Theor. Comput. Sci. 382(2), 139–150 (2007)
Miller, R.E., Muller, D.E.: A problem of maximum consistent subsets. IBM Research Report RC-240, J. T. Watson Research Center (1960)
Moon, J.W., Moser, L.: On cliques in graphs. Israel J. Math. 3, 23–28 (1965)
Niedermeier, R., Rossmanith, P.: An efficient fixed-parameter algorithm for 3-hitting set. J. Discrete Algorithms 1(1), 89–102 (2003)
Wahlström, M.: Exact algorithms for finding minimum transversals in rank-3 hypergraphs. J. Algorithms 51(2), 107–121 (2004)
Wahlström, M.: Algorithms, measures and upper bounds for satisfiability and related problems. Ph.D. thesis, Linköping University, Sweden (2007)
Acknowledgments
We thank Fabrizio Grandoni for initial discussions on this research. Dieter Kratsch acknowledges support from the French Research Agency, project GraphEn (ANR-15-CE40-0009). Serge Gaspers is the recipient of an Australian Research Council (ARC) Future Fellowship (project FT140100048) and acknowledges support under the ARC’s Discovery Projects funding scheme (project DP150101134). NICTA is funded by the Australian Government through the Department of Communications and the ARC through the ICT Centre of Excellence Program.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2016 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Cochefert, M., Couturier, JF., Gaspers, S., Kratsch, D. (2016). Faster Algorithms to Enumerate Hypergraph Transversals. In: Kranakis, E., Navarro, G., Chávez, E. (eds) LATIN 2016: Theoretical Informatics. LATIN 2016. Lecture Notes in Computer Science(), vol 9644. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-49529-2_23
Download citation
DOI: https://doi.org/10.1007/978-3-662-49529-2_23
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-49528-5
Online ISBN: 978-3-662-49529-2
eBook Packages: Computer ScienceComputer Science (R0)