Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network. (English) Zbl 1213.05251

Mezzini, Mauro; Moscarini, Marina

Theor. Comput. Sci. 411, No. 7-9, 958-966 (2010).

Summary: We propose a simple algorithm called CliqueMinTriang for computing a minimal triangulation of a graph. If \(F\) is the set of edges that is added to \(G\) to make it a complete graph \(K_n\) then the asymptotic complexity of CliqueMinTriang is \(O(|F|(\delta ^{2}+|F|))\) where \(\delta \) is the degree of the subgraph of \(K_n\) induced by \(F\). Therefore our algorithm performs well when \(G\) is a dense graph. We also show how to exploit the existing minimal triangulation techniques in conjunction with CliqueMinTriang to efficiently find a minimal triangulation of nondense graphs. Finally we show how the algorithm can be adapted to perform a backward stepwise selection of decomposable Markov networks; the resulting procedure has the same time complexity as that of existing similar algorithms.

MSC:

05C85	Graph algorithms (graph-theoretic aspects)
68R10	Graph theory (including graph drawing) in computer science

Keywords:

chordal graphs; minimal triangulations; Markov networks; learning decomposable models

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
[2]	Berry, A.; Blair, J. R.S.; Heggernes, P.; Peyton, B. W., Maximum cardinality search for computing minimal triangulations of graphs, Algorithmica, 39, 4, 287-298 (2004) · Zbl 1090.68080
[3]	Berry, A.; Bordat, J. P.; Heggernes, P.; Simonet, G.; Villanger, Y., A wide-range algorithm for minimal triangulation from an arbitrary ordering, J. Algorithms, 58, 1, 33-66 (2006) · Zbl 1093.68137
[4]	Blair, J. R.S.; Heggernes, P.; Telle, J. A., A practical algorithm for making filled graphs minimal, Theoret. Comput. Sci., 250, 1-2, 125-141 (2001) · Zbl 0952.68104
[5]	Blair, J. R.S.; Peyton, B. W., An introduction to chordal graphs and clique trees, (George, J. A.; Gilbert, J. R.; Liu, J. W.H., Sparse Matrix Computations: Graph Theory Issues and Algorithms. Sparse Matrix Computations: Graph Theory Issues and Algorithms, IMA Volumes in Mathematics and its Applications, 56 (1993), Springer Verlag), 1-30 · Zbl 0803.68081
[6]	R. Boisvert, R. Pozo, K. Remington, B. Miller, R. Lipman, NIST MatrixMarket. http://math.nist.gov/MatrixMarket/index.html; R. Boisvert, R. Pozo, K. Remington, B. Miller, R. Lipman, NIST MatrixMarket. http://math.nist.gov/MatrixMarket/index.html
[7]	A. Deshpande, M.N. Garofalakis, M.I. Jordan, Efficient stepwise selection in decomposable models, In: UAI, 2001, pp. 128-135; A. Deshpande, M.N. Garofalakis, M.I. Jordan, Efficient stepwise selection in decomposable models, In: UAI, 2001, pp. 128-135
[8]	Ding, G.; Lax, R. F.; Chen, J.; Chen, P. P.; Marx, B. D., Comparison of greedy strategies for learning markov networks of treewidth k, (Arabnia, H. R.; Dehmer, M.; Emmert-Streib, F.; Yang, M. Q., Proceedings of the 2007 International Conference on Machine Learning (2007), CSREA Press: CSREA Press Las Vegas Nevada, USA), 294
[9]	Heggernes, P., Minimal triangulations of graphs: A survey, Discrete Math., 306, 3, 297-317 (2006) · Zbl 1086.05069
[10]	P. Heggernes, B. Peyton, Fast computation of minimal fill inside a given elimination ordering, SIAM J. Matrix Anal. Appl. 2008, (in press); P. Heggernes, B. Peyton, Fast computation of minimal fill inside a given elimination ordering, SIAM J. Matrix Anal. Appl. 2008, (in press) · Zbl 1176.65027
[11]	Heggernes, P.; Telle, J. A.; Villanger, Y., Computing minimal triangulations in time \(o(n^\alpha \log n) = o(n^{2.376})\), SIAM J. Discret. Math., 19, 4, 900-913 (2005) · Zbl 1105.05066
[12]	Ibarra, L., Fully dynamic algorithms for chordal graphs and split graphs, ACM Trans. Algorithms, 4, 4, 1-20 (2008) · Zbl 1445.05103
[13]	Kullback, S.; Leibler, R. A., On information and sufficiency, Ann. Math. Statist, 22, 1, 79-86 (1951) · Zbl 0042.38403
[14]	Malvestuto, F., Approximating discrete probability distributions with decomposable models, IEEE Trans. Syst. Man Cybern., 21, 5, 1287-1294 (1991)
[15]	Malvestuto, F. M., Existence of extensions and product extensions for discrete probability distributions, Discrete Math., 69, 1, 61-77 (1988) · Zbl 0637.60021
[16]	Rose, D. J.; Tarjan, R. E.; Lueker, G. S., Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., 5, 2, 266-283 (1976) · Zbl 0353.65019
[17]	N. Srebro, Maximum likelihood markov networks: An algorithmic approach, MSc Thesis, Massachusetts Institute of Technology. http://ttic.uchicago.edu/ nati/Publications/Mthesis.pdf; N. Srebro, Maximum likelihood markov networks: An algorithmic approach, MSc Thesis, Massachusetts Institute of Technology. http://ttic.uchicago.edu/ nati/Publications/Mthesis.pdf
[18]	N. Srebro, Maximum likelihood bounded tree-width markov networks, in: UAI ’01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA, pp. 504-511, 2001; N. Srebro, Maximum likelihood bounded tree-width markov networks, in: UAI ’01: Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, University of Washington, Seattle, Washington, USA, pp. 504-511, 2001
[19]	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, 3, 566-579 (1984) · Zbl 0545.68062
[20]	Yannakakis, M., Computing the minimum fill-in is np-complete, SIAM. J. Algebr. Discrete Methods, 2, 1, 77-79 (1981) · Zbl 0496.68033