Abstract
We investigate the computational complexity of two decision problems concerning the existence of certain acyclic subhypergraphs of a given hypergraph, namely the Spanning Acyclic Subhypergraph problem and the Maximum Acyclic Subhypergraph problem. The former is about the existence of an acyclic subhypergraph such that each vertex of the input hypergraph is contained in at least one hyperedge of the subhypergraph. The latter is about the existence of an acyclic subhypergraph with k hyperedges where k is part of the input. For each of these problems, we consider different notions of acyclicity of hypergraphs: Berge-acyclicity, γ-acyclicity, β-acyclicity and α-acyclicity. We are also concerned with the size of the hyperedges of the input hypergraph. Depending on these two parameters (notion of acyclicity and size of the hyperedges), we try to determine which instances of the two problems are in P ∩ RNC and which are NP-complete.
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., Mendelzon, A., Ullman, J., Yannakakis, M.: Properties of acyclic database schemes. In: Proceedings of the 13th Annual ACM Symposium on Theory of Computing, pp. 355–362 (1981)
Berge, C.: Graphs and hypergraphs. North-Holland, Amsterdam (1976)
Brouwer, A.E., Kolen, A.W.J.: A super-balanced hypergraph has a nest point. Technical report, Stichting Mathematisch Centrum (1980)
Duris, D.: Hypergraph acyclicity and extension preservation theorems. In: Proceedings of the 23rd Annual IEEE Symposium on Logic in Computer Science, pp. 418–427 (2008)
Fagin, R.: Degrees of acyclicity for hypergraphs and relational database schemes. Journal of the ACM 30(3), 514–550 (1983)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1990)
Goodall, A., de Mier, A.: Spanning trees of 3-uniform hypergraphs. Preprint available as arXiv:1002.3331v1 (February 2010)
Greenlaw, R., Hoover, H.J., Ruzzo, W.L.: Limits to parallel computation: P-completeness theory. Oxford University Press, USA (1995)
Halperin, S., Zwick, U.: Optimal randomized EREW PRAM algorithms for finding spanning forests and for other basic graph connectivity problems. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 438–447. SIAM, Philadelphia (1996)
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)
Kasteleyn, P.W.: The statistics of dimers on a lattice. Physica 27(12), 1209–1225 (1961)
Lovász, L.: Matroid matching and some applications. Journal of Combinatorial Theory, Series B 28(2), 208–236 (1980)
Masbaum, G., Caracciolo, S., Sokal, A., Sportiello, A.: A randomized polynomial-time algorithm for the spanning hypertree problem on 3-uniform hypergraphs. Preprint available as arXiv:0812.3593
Masbaum, G., Vaintrob, A.: A new matrix-tree theorem. International Mathematics Research Notices (27), 1397 (2002)
Schwartz, J.: Fast probabilistic algorithms for verification of polynomial identities. Journal of the ACM 27, 701–717 (1980)
Wang, J., Li, H.: Counting acyclic hypergraphs. Science in China Series A: Mathematics 44(2), 220–224 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Duris, D., Strozecki, Y. (2011). The Complexity of Acyclic Subhypergraph Problems. In: Katoh, N., Kumar, A. (eds) WALCOM: Algorithms and Computation. WALCOM 2011. Lecture Notes in Computer Science, vol 6552. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-19094-0_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-19094-0_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-19093-3
Online ISBN: 978-3-642-19094-0
eBook Packages: Computer ScienceComputer Science (R0)