Abstract
An acyclic subhypergraph of a hypergraph is maximal if there exists no acyclic subhypergraph containing it. In this paper, first we show that, unless P=NP, there is no polynomial delay algorithm for generating all maximal acyclic subhypergraphs in lexicographic order. Next, by ignoring the order of outputs, we design a polynomial delay algorithm for generating all maximal acyclic subhypergraphs.
This work is partially supported by Grand-in-Aid for Scientific Research 19300046 from the Ministry of Education, Culture, Sports, Science and Technology, Japan.
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
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Beeri, C., Fagin, R., Maier, D., Yannakakis, M.: On the desirability of acyclic database schemes. J. ACM 30, 479–513 (1983)
Berge, C.: Graphs and hypergraphs. North-Holland, Amsterdam (1973)
Berge, C.: Hypergraphs. North-Holland, Amsterdam (1989)
Chekuri, C., Rajaraman, A.: Conjunctive query containment revisited. Theoret. Comput. Sci. 239, 211–229 (2000)
D’Atri, A., Moscarini, M.: On hypergraph acyclicity and graph chordality. Inform. Proc. Lett. 29, 271–274 (1988)
Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. JACM 30, 514–550 (1983)
Gabow, H.N., Myers, E.W.: Finding all spanning trees of directed and undirected graphs. SIAM J. Comput. 7, 280–287 (1978)
Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. W. H. Freeman and Company, New York (1979)
Gottlob, G., Leone, N., Scarcello, F.: The complexity of acyclic conjunctive queries. J. ACM 43, 431–498 (2001)
Hirata, K., Kuwabara, M., Harao, M.: On finding acyclic subhypergraphs. In: Liśkiewicz, M., Reischuk, R. (eds.) FCT 2005. LNCS, vol. 3623, pp. 491–503. Springer, Heidelberg (2005)
Horváth, T., Bringmann, B., de Raedt, L.: Frequent hypergraph mining. In: Muggleton, S., Otero, R., Tamaddoni-Nezhad, A. (eds.) ILP 2006. LNCS (LNAI), vol. 4455, pp. 244–259. Springer, Heidelberg (2007)
Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inform. Proc. Let. 27, 119–123 (1988)
Kapoor, S., Ramesh, H.: Algorithms for generating all spanning trees of undirected and weighted graphs. SIAM J. Comput. 24, 247–265 (1995)
Lovász, L.: Combinatorial problems and exercises. North-Holland, Amsterdam (1979)
Shioura, A., Tamura, A., Uno, T.: An optimal algorithm for scanning all spanning trees of undirected graphs. SIAM J. Comput. 26, 678–692 (1997)
Tarjan, R.E., Yannakakis, M.: Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs. SIAM J. Comput. 13, 566–579 (1984)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Daigo, T., Hirata, K. (2009). On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay. In: Nielsen, M., Kučera, A., Miltersen, P.B., Palamidessi, C., Tůma, P., Valencia, F. (eds) SOFSEM 2009: Theory and Practice of Computer Science. SOFSEM 2009. Lecture Notes in Computer Science, vol 5404. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-95891-8_19
Download citation
DOI: https://doi.org/10.1007/978-3-540-95891-8_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-95890-1
Online ISBN: 978-3-540-95891-8
eBook Packages: Computer ScienceComputer Science (R0)