×

Computing the union join and subset graph of acyclic hypergraphs in subquadratic time. (English) Zbl 07498704

Lubiw, Anna (ed.) et al., Algorithms and data structures. 17th international symposium, WADS 2021, virtual event, August 9–11, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12808, 571-584 (2021).
Summary: We investigate the two problems of computing the union join graph as well as computing the subset graph for acyclic hypergraphs and their subclasses. In the union join graph \(G\) of an acyclic hypergraph \(H\), each vertex of \(G\) represents a hyperedge of \(H\) and two vertices of \(G\) are adjacent if there exits a join tree \(T\) for \(H\) such that the corresponding hyperedges are adjacent in \(T\). The subset graph of a hypergraph \(H\) is a directed graph where each vertex represents a hyperedge of \(H\) and there is a directed edge from a vertex \(u\) to a vertex \(v\) if the hyperedge corresponding to \(u\) is a subset of the hyperedge corresponding to \(v\).
For a given hypergraph \(H = (V, \mathcal{E})\), let \(n = |V|\), \(m = |\mathcal{E}|\), and \(N = \sum_{E \in \mathcal{E}} |E|\). We show that, if the Strong Exponential Time Hypothesis is true, both problems cannot be solved in \(\mathcal{O}\bigl ( N^{2 - \varepsilon } \bigr )\) time for \(\alpha \)-acyclic hypergraphs and any constant \(\varepsilon > 0\), even if the created graph is sparse. Additionally, we present algorithms that solve both problems in \(\mathcal{O}\bigl ( N^2 / \log N + |G| \bigr )\) time for \(\alpha \)-acyclic hypergraphs, in \(\mathcal{O}\bigl ( N \log (n + m) + |G| \bigr )\) time for \(\beta \)-acyclic hypergraphs, and in \(\mathcal{O}\bigl ( N + |G| \bigr )\) time for \(\gamma \)-acyclic hypergraphs as well as for interval hypergraphs, where \(|G|\) is the size of the computed graph.
For the entire collection see [Zbl 1482.68032].

MSC:

68P05 Data structures
68Wxx Algorithms in computer science
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 3, 479-513 (1983) · Zbl 0624.68087 · doi:10.1145/2402.322389
[2] Berry, A., Simonet, G.: Computing the atom graph of a graph and the union join graph of a hypergraph. CoRR abs/1607.02911 (2016)
[3] Borassi, M.; Crescenzi, P.; Habib, M., Into the square: on the complexity of some quadratic-time solvable problems, Electron. Notes Theor. Comput. Sci., 322, 51-67 (2016) · Zbl 1345.68170 · doi:10.1016/j.entcs.2016.03.005
[4] Brandstädt, A., Dragan, F.F.: Tree-structured graphs. In: Handbook of Graph Theory, Combinatorial Optimization, and Algorithms, pp. 751-826. CRC Press (2015) · Zbl 1388.05034
[5] Brandstädt, A.; Dragan, FF; Chepoi, V.; Voloshin, VI, Dually chordal graphs, SIAM J. Discret. Math., 11, 3, 437-455 (1998) · Zbl 0909.05037 · doi:10.1137/S0895480193253415
[6] Dourisboure, Y., Compact routing schemes for generalised chordal graphs, J. Graph Algorithms Appl., 9, 2, 277-297 (2005) · doi:10.7155/jgaa.00109
[7] Dourisboure, Y.; Dragan, FF; Gavoille, C.; Yan, C., Spanners for bounded tree-length graphs, Theoret. Comput. Sci., 383, 1, 34-44 (2007) · Zbl 1123.68087 · doi:10.1016/j.tcs.2007.03.058
[8] Dragan, FF; Köhler, E., An approximation algorithm for the tree t-spanner problem on unweighted graphs via generalized chordal graphs, Algorithmica, 69, 4, 884-905 (2013) · Zbl 1303.05186 · doi:10.1007/s00453-013-9765-4
[9] Elmasry, A., Computing the subset partial order for dense families of sets, Inf. Process. Lett., 109, 18, 1082-1086 (2009) · Zbl 1202.68473 · doi:10.1016/j.ipl.2009.07.001
[10] Fagin, R., Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 30, 3, 514-550 (1983) · Zbl 0624.68088 · doi:10.1145/2402.322390
[11] Galinier, P.; Habib, M.; Paul, C.; Nagl, M., Chordal graphs and their clique graphs, Graph-Theoretic Concepts in Computer Science, 358-371 (1995), Heidelberg: Springer, Heidelberg · Zbl 07810379 · doi:10.1007/3-540-60618-1_88
[12] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. Comb. Theory Ser. B, 16, 1, 47-56 (1974) · Zbl 0266.05101 · doi:10.1016/0095-8956(74)90094-X
[13] Habib, M.; McConnell, RM; Paul, C.; Viennot, L., LEX-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Theor. Comput. Sci., 234, 1-2, 59-84 (2000) · Zbl 0945.68189 · doi:10.1016/S0304-3975(97)00241-7
[14] Habib, M.; Stacho, J., Reduced clique graphs of chordal graphs, Eur. J. Comb., 33, 5, 712-735 (2012) · Zbl 1237.05139 · doi:10.1016/j.ejc.2011.09.031
[15] Kaba, B.; Pinet, N.; Lelandais, G.; Sigayret, A.; Berry, A., Clustering gene expression data using graph separators, Silico Biol., 7, 4-5, 433-452 (2007)
[16] Leimer, H., Optimal decomposition by clique separators, Discret. Math., 113, 1-3, 99-123 (1993) · Zbl 0793.05128 · doi:10.1016/0012-365X(93)90510-Z
[17] Leitert, A.: Computing the union join and subset graph of acyclic hypergraphs in subquadratic time. CoRR abs/2104.06636 (2021)
[18] Paige, R.; Tarjan, RE, Three partition refinement algorithms, SIAM J. Comput., 16, 6, 973-989 (1987) · Zbl 0654.68072 · doi:10.1137/0216062
[19] Pritchard, P., Opportunistic algorithms for eliminating supersets, Acta Inform., 28, 8, 733-754 (1991) · Zbl 0724.68045 · doi:10.1007/BF01261654
[20] Pritchard, P., On computing the subset graph of a collection of sets, J. Algorithms, 33, 2, 187-203 (1999) · Zbl 0948.68216 · doi:10.1006/jagm.1999.1032
[21] Tarjan, RE; Yannakakis, M., Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs, SIAM J. Comput., 13, 3, 566-579 (1984) · Zbl 0545.68062 · doi:10.1137/0213035
[22] Uehara, R.; Uno, Y., Laminar structure of ptolemaic graphs with applications, Discret. Appl. Math., 157, 7, 1533-1543 (2009) · Zbl 1177.05122 · doi:10.1016/j.dam.2008.09.006
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.