Decomposition of a hypergraph by partial-edge separators. (English) Zbl 0939.68089

Malvestuto, F. M.; Moscarini, M.

Theor. Comput. Sci. 237, No. 1-2, 57-79 (2000).

Summary: The notion of vertex separability by partial edges for a simple hypergraph is introduced and the related structural properties of the hypergraph are analyzed in terms of maximal (with respect to set-theoretic inclusion) compacts and of dividers, where a compact is a vertex set in which every two vertices are separated by no partial edge, and a divider is a partial edge \(X\) for which there exists a pair of vertices that are separated by \(X\) and by no proper subset of \(X\). It is proven that, given a hypergraph \(H\), the hypergraph (called the compaction of \(H\)) made up of maximal compacts of \(H\) is acyclic and coincides with \(H\) if and only if \(H\) is acyclic; furthermore, it has the same dividers as \(H\), and can be characterized as being the unique acyclic hypergraph that has the same compacts as \(H\). Polynomial algorithms for finding maximal compacts and dividers of a given hypergraph are provided. Finally, an application to the problem of computing the maximum-entropy extension of a system of marginals over a hypergraph is discussed.

MSC:

68R10

Graph theory (including graph drawing) in computer science

Keywords:

separator; decomposition; acyclicity; compaction

References:

[1]	Asmussen, S.; Edwards, D., Collapsibility and response variables in contingency tables, Biometrika, 70, 567-578 (1983) · Zbl 0549.62041
[2]	Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. Assoc. Comput. Machinery, 30, 479-513 (1983) · Zbl 0624.68087
[3]	C. Berge, Hypergraphs, North-Holland, Amsterdam, 1989.; C. Berge, Hypergraphs, North-Holland, Amsterdam, 1989. · Zbl 0674.05001
[4]	Y.M. Bishop, S. Fienberg, P. Holland, Discrete Multivariate Analysis, MIT Press, Cambridge, MA, 1975.; Y.M. Bishop, S. Fienberg, P. Holland, Discrete Multivariate Analysis, MIT Press, Cambridge, MA, 1975. · Zbl 0332.62039
[5]	Darroch, J. N.; Lauritzen, S. L.; Speed, T. P., Markov fields and loglinear interaction models for contingency tables, Ann. Statist., 8, 522-539 (1980) · Zbl 0444.62064
[6]	S. Even, Graph Algorithms, Pitman, London, 1979.; S. Even, Graph Algorithms, Pitman, London, 1979. · Zbl 0441.68072
[7]	A. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969.; A. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1969. · Zbl 0182.57702
[8]	Jirousek, R.; Preucil, S., On the effective implementation of the iterative proportional fitting procedure, Comput. Statist. Data Anal., 19, 177-189 (1995) · Zbl 0875.65122
[9]	Lauritzen, S. L.; Speed, T. P.; Vijayan, K., Decomposable graphs and hypergraphs, J. Australian Math. Soc. Ser. A, 36, 12-29 (1984) · Zbl 0533.05046
[10]	Leimer, G., Optimal decomposition by clique separators, Discrete Math., 113, 99-123 (1993) · Zbl 0793.05128
[11]	Malvestuto, F. M., Computing the maximum-entropy extension of given discrete probability distributions, Comput. Statist. Data Anal., 8, 299-311 (1989) · Zbl 0726.62012
[12]	Malvestuto, F. M., Testing implication of hierarchical log-linear models for probability distributions, Statist. Comput., 6, 169-176 (1996)
[13]	F.M. Malvestuto, M. Moscarini, A fast algorithm for query optimization in universal-relation databases, Proc. 3rd Italian Conf. on Advanced Database Systems (“Sistemi Evoluti per Basi di Dati”), Ravello, 1995; J. Comput. System Sci. 56 (1998) 299-309.; F.M. Malvestuto, M. Moscarini, A fast algorithm for query optimization in universal-relation databases, Proc. 3rd Italian Conf. on Advanced Database Systems (“Sistemi Evoluti per Basi di Dati”), Ravello, 1995; J. Comput. System Sci. 56 (1998) 299-309. · Zbl 0913.68060
[14]	Tarjan, R. E., Decomposition by clique separators, Discrete Math., 55, 221-232 (1985) · Zbl 0572.05039