×

zbMATH — the first resource for mathematics

Treewidth computations. I: Upper bounds. (English) Zbl 1186.68328
Summary: For more and more applications, it is important to be able to compute the treewidth of a given graph and to find tree decompositions of small width reasonably fast.
This paper gives an overview of several upper bound heuristics that have been proposed and tested for the problem of determining the treewidth of a graph and finding tree decompositions. Each of the heuristics produces tree decompositions whose width may be larger than the optimal width. However, experiments show that in many cases, the heuristics give tree decompositions whose width is close to the exact treewidth of the input graphs.

MSC:
68R10 Graph theory (including graph drawing) in computer science
68W10 Parallel algorithms in computer science
68W25 Approximation algorithms
05C85 Graph algorithms (graph-theoretic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnborg, S.; Proskurowski, A., Linear time algorithms for NP-hard problems restricted to partial k-trees, Disc. appl. math., 23, 11-24, (1989) · Zbl 0666.68067
[2] Bern, M.W.; Lawler, E.L.; Wong, A.L., Linear time computation of optimal subgraphs of decomposable graphs, J. algorithm, 8, 216-235, (1987) · Zbl 0618.68058
[3] Koster, A.M.C.A.; van Hoesel, S.P.M.; Kolen, A.W.J., Solving partial constraint satisfaction problems with tree decomposition, Networks, 40, 3, 170-180, (2002) · Zbl 1027.90072
[4] Telle, J.A.; Proskurowski, A., Algorithms for vertex partitioning problems on partial k-trees, SIAM J. disc. math., 10, 529-550, (1997) · Zbl 0885.68118
[5] Wimer, T.V.; Hedetniemi, S.T.; Laskar, R., A methodology for constructing linear graph algorithms, Congressus numerantium, 50, 43-60, (1985) · Zbl 0603.68040
[6] Y. Song, C. Liu, R. Malmberg, F. Pan, L. Cai, Tree decomposition based fast search of RNA structures including pseudoknots in genomes, in: CSB’05: Proceedings of the 2005 IEEE Computational Systems Bioinformatics Conference, IEEE Computer Society, Washington, DC, USA, 2005, pp. 223-234. doi:10.1109/CSB.2005.52.
[7] J. Zhao, D. Che, L. Cai, Comparative pathway annotation with protein-DNA interaction and operon information via graph tree decomposition, in: Proceedings of Pacific Symposium on Biocomputing (PSB 2007), vol. 12, 2007, pp. 496-507.
[8] Zhao, J.; Malmberg, R.L.; Cai, L., Rapid ab initio prediction of RNA pseudoknots via graph tree decomposition, J. math. biol., 243-282, (2000)
[9] H. Chen, Quantified constraint satisfaction and bounded treewidth, in: R.L. de Mántaras, L. Saitta (Eds.), Proceedings of the 16th European Conference on Artificial Intelligence, ECAI’2004, 2004, pp. 161-165.
[10] Gottlob, G.; Leone, N.; Scarcello, F., A comparison of structural CSP decomposition methods, Acta inform., 124, 243-282, (2000) · Zbl 0952.68044
[11] Lauritzen, S.J.; Spiegelhalter, D.J., Local computations with probabilities on graphical structures and their application to expert systems, J. roy. stat. soc. ser. B, 50, 157-224, (1988) · Zbl 0684.68106
[12] Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM J. comput., 25, 1305-1317, (1996) · Zbl 0864.68074
[13] H. Röhrig, Tree decomposition: a feasibility study, Master’s thesis, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1998.
[14] A.M.C.A. Koster, ComputeTW - An interactive platform for computing Treewidth of graphs. URL:http://www.math2.rwth-aachen.de/ koster/computeTW/, 2009.
[15] H.L. Bodlaender, A.M.C.A. Koster, Treewidth computations II. Lower bounds, in preparation. · Zbl 1220.68071
[16] H.L. Bodlaender, A.M.C.A. Koster, Treewidth computations III. Exact algorithms and preprocessing, in preparation.
[17] Berge, C., Graphs, (1985), North-Holland Amsterdam · Zbl 0334.05117
[18] Bollobás, B., Modern graph theory, graduate texts in mathematics, (1998), Springer New York
[19] Gross, J.; Yellen, J., Graph theory and its applications, (1999), CRC Press New York · Zbl 0920.05001
[20] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[21] Tutte, W.T., Graph theory, Encyclopedia of mathematics and its applications, vol. 21, (1984), Addison-Wesley Menlo Park, CA · Zbl 0554.05001
[22] West, D.B., Introduction to graph theory, (2001), Prentice-Hall Englewood Cliffs, NJ
[23] Brandstädt, A.; Le, V.; Spinrad, J.P., Graph classes. A survey, SIAM monographs on discrete mathematics and applications, (1999), SIAM Philadelphia, PA
[24] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C., Introduction to algorithms, (2001), MIT Press Cambridge, MA · Zbl 1047.68161
[25] Even, S., Graph algorithms, (1979), Pitman London · Zbl 0441.68072
[26] Gibbons, A.M., Algorithmic graph theory, (1985), Cambridge University Press Cambridge · Zbl 0568.05001
[27] Kleinberg, J.; Tardos, Éva, Algorithm design, (2005), Addison-Wesley Boston, MA
[28] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[29] Downey, R.G.; Fellows, M.R., Parameterized complexity, (1999), Springer Berlin · Zbl 0914.68076
[30] Flum, J.; Grohe, M., Parameterized complexity theory, (2006), Springer Berlin
[31] Niedermeier, R., Invitation to fixed-parameter algorithms, Oxford lecture series in mathematics and its applications, (2006), Oxford University Press Oxford · Zbl 1095.68038
[32] Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of NP-completeness, (1979), W.H. Freeman New York · Zbl 0411.68039
[33] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability – a survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018
[34] Bodlaender, H.L., A tourist guide through treewidth, Acta cybernetica, 11, 1-23, (1993) · Zbl 0804.68101
[35] Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth, Theor. comput. sci., 209, 1-45, (1998) · Zbl 0912.68148
[36] Bodlaender, H.L., Discovering treewidth, (), 1-16 · Zbl 1117.68451
[37] Bodlaender, H.L.; Koster, A.M.C.A., Combinatorial optimization on graphs of bounded treewidth, Comput. J., 51, 3, 255-269, (2008)
[38] I.V. Hicks, A.M.C.A. Koster, E. Kolotoğlu, Branch and tree decomposition techniques for discrete optimization, in: J.C. Smith (Ed.), TutORials 2005, INFORMS Tutorials in Operations Research Series, INFORMS Annual Meeting, 2005, pp. 1-29 (Chapter 1).
[39] Koster, A.M.C.A.; Bodlaender, H.L.; van Hoesel, S.P.M., Treewidth: computational experiments, (), 54-57 · Zbl 1409.05176
[40] Reed, B.A., Tree width and tangles: a new measure of connectivity and some applications, (), 87-162 · Zbl 0895.05034
[41] Reed, B.A., Algorithmic aspects of tree width, (), 85-107 · Zbl 1035.05090
[42] Kloks, T., Treewidth. computations and approximations, Lecture notes in computer science, vol. 842, (1994), Springer Berlin
[43] Hliněný, P.; Oum, S.; Seese, D.; Gottlob, G., Width parameters beyond tree-width and their applications, Comput. J., 51, 326-362, (2008)
[44] Robertson, N.; Seymour, P.D., Graph minors. II. algorithmic aspects of tree-width, J. algorithm, 7, 309-322, (1986) · Zbl 0611.05017
[45] Bodlaender, H.L.; Möhring, R.H., The pathwidth and treewidth of cographs, SIAM J. disc. math., 6, 181-188, (1993) · Zbl 0773.05091
[46] Gavril, F., The intersection graphs of subtrees in trees are exactly the chordal graphs, J. comb. theory B, 16, 47-56, (1974) · Zbl 0266.05101
[47] Buneman, P., A characterization of rigid circuit graphs, Disc. math., 9, 205-212, (1974) · Zbl 0288.05128
[48] Dirac, G., On rigid circuit graphs, Abh. math. sem. univ. Hamburg, 25, 71-76, (1961) · Zbl 0098.14703
[49] Fulkerson, D.R.; Gross, O.A., Incidence matrices and interval graphs, Pacific J. math., 15, 835-855, (1965) · Zbl 0132.21001
[50] Rose, D.J.; Tarjan, R.E.; Lueker, G.S., Algorithmic aspects of vertex elimination on graphs, SIAM J. comput., 5, 266-283, (1976) · Zbl 0353.65019
[51] Walter, J., Representations of chordal graphs as subgraphs of a tree, J. graph theory, 2, 265-267, (1978) · Zbl 0441.05022
[52] Parter, S., The use of linear graphs in Gauss elimination, SIAM rev., 3, 119-130, (1961) · Zbl 0102.11302
[53] Rose, D.J., Triangulated graphs and the elimination process, J. math. anal. appl., 32, 597-609, (1970) · Zbl 0216.02602
[54] Berry, A.; Dahlhaus, E.; Heggernes, P.; Simonet, G., Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Theor. comput. sci., 409, 601-616, (2008) · Zbl 1155.68088
[55] Tarjan, R.E.; Yannakakis, M., Simple linear time algorithms to test chordiality of graphs, test acyclicity of graphs, and selectively reduce acyclic hypergraphs, SIAM J. comput., 13, 566-579, (1984) · Zbl 0545.68062
[56] Berry, A.; Blair, J.R.S.; Heggernes, P., Maximum cardinality search for computing minimal triangulations, (), 1-12 · Zbl 1022.68088
[57] Berry, A.; Blair, J.; Heggernes, P.; Peyton, B., Maximum cardinality search for computing minimal triangulations of graphs, Algorithmica, 39, 287-298, (2004) · Zbl 1090.68080
[58] Villanger, Y., Lex M versus MCS-M, Disc. math., 306, 393-400, (2006) · Zbl 1084.05071
[59] Berry, A.; Krueger, R.; Simonet, G., Ultimate generalizations of lexbfs and LEX M, (), 199-213 · Zbl 1171.68589
[60] Markowitz, H.M., The elimination form of the inverse and its application to linear programming, Manage. sci., 3, 255-269, (1957) · Zbl 0995.90592
[61] Berry, A.; Heggernes, P.; Simonet, G., The minimum degree heuristic and the minimal triangulation process, (), 58-70 · Zbl 1255.05186
[62] Clautiaux, F.; Carlier, J.; Moukrim, A.; Négre, S., New lower and upper bounds for graph treewidth, (), 70-80 · Zbl 1023.68645
[63] Clautiaux, F.; Moukrim, A.; Négre, S.; Carlier, J., Heuristic and meta-heuristic methods for computing graph treewidth, RAIRO operat. res., 38, 13-26, (2004) · Zbl 1092.90065
[64] Bachoore, E.H.; Bodlaender, H.L., New upper bound heuristics for treewidth, (), 217-227 · Zbl 1121.68355
[65] Bodlaender, H.L.; Koster, A.M.C.A.; Eijkhof, F.v.d., Pre-processing rules for triangulation of probabilistic networks, Comput. intell., 21, 3, 286-305, (2005)
[66] A. Cano, S. Moral, Heuristic algorithms for the triangulation of graphs, in: B. Bouchon-Meunier, R.R. Yager, I.A. Zadeh (Eds.), Advances in Intelligent Computing, Selected Papers from the Fifth International Conference on Precessing and Management of Uncertainty in Knowledge-Based Systems IPMU94, Lecture Notes in Computer Science, vol. 945, Springer, Berlin, 1994, pp. 98-107.
[67] Heggernes, P.; Villanger, Y., Simple and efficient modifications of elimination orderings, (), 788-797
[68] Kjærulff, U., Optimal decomposition of probabilistic networks by simulated annealing, Stat. comput., 2, 2-17, (1992)
[69] Larrañaga, P.; Kuijpers, C.M.H.; Poza, M.; Murga, R.H., Decomposing Bayesian networks: triangulation of the moral graph with genetic algorithms, Stat. comput. (UK), 7, 1, 19-34, (1997)
[70] B. Marchal, C.v. Hoesel, A.M.C.A. Koster, A local search algorithm for determining tree decompositions of graphs, in: Presented on the International Symposium on Combinatorial Optimization, March 2008.
[71] Hoesel, C.P.M.v.; Marchal, B., Finding good tree decompositions by local search, Electron. notes dis. math., 32, 43-50, (2009) · Zbl 1267.05273
[72] Gogate, V.; Dechter, R., A complete anytime algorithm for treewidth, (), 201-208
[73] Bodlaender, H.L.; Fomin, F.V.; Koster, A.M.C.A.; Kratsch, D.; Thilikos, D.M., On exact algorithms for treewidth, (), 672-683 · Zbl 1131.68481
[74] E. Amir, Efficient approximation for triangulation of minimum treewidth, in: Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence, 2001, pp. 7-15.
[75] E. Amir, Approximation algorithms for treewidth, algorithmica, published online 2008.
[76] Becker, A.; Geiger, D., A sufficiently fast algorithm for finding close to optimal clique trees, Artif. intell., 125, 3-17, (2001) · Zbl 0972.68152
[77] Bouchitté, V.; Kratsch, D.; Müller, H.; Todinca, I., On treewidth approximations, Disc. appl. math., 136, 183-196, (2004) · Zbl 1035.05087
[78] Bodlaender, H.L.; Gilbert, J.R.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize, and minimum elimination tree height, J. algorithm, 18, 238-255, (1995) · Zbl 0818.68118
[79] Diestel, R.; Jensen, T.R.; Gorbunov, K.Y.; Thomassen, C., Highly connected sets and the excluded grid theorem, J. comb. theory B, 75, 61-73, (1999) · Zbl 0949.05075
[80] Lagergren, J., Efficient parallel algorithms for graphs of bounded tree-width, J. algorithm, 20, 20-44, (1996) · Zbl 0840.68058
[81] Reed, B., Finding approximate separators and computing tree-width quickly, (), 221-228
[82] Robertson, N.; Seymour, P.D., Graph minors. XIII. the disjoint paths problem, J. comb. theory B, 63, 65-110, (1995) · Zbl 0823.05038
[83] Gilbert, J.R.; Rose, D.J.; Edenbrandt, A., A separator theorem for chordal graphs, SIAM J. alg. disc. meth., 5, 306-313, (1984) · Zbl 0551.05049
[84] Liu, J.W.H., The role of elimination trees in sparse factorization, SIAM J. matrix anal. appl., 11, 134-172, (1990) · Zbl 0697.65013
[85] A.M.C.A. Koster, Frequency assignment – models and algorithms, Ph.D. Thesis, University of Maastricht, Maastricht, The Netherlands, 1999.
[86] Blair, J.R.S.; Heggernes, P.; Telle, J., A practical algorithm for making filled graphs minimal, Theor. comput. sci., 250, 125-141, (2001) · Zbl 0952.68104
[87] A. Berry, A wide-range efficient algorithm for minimal triangulation, in: SODA’99: ACM-SIAM Symposium on Discrete Algorithms, 1999, pp. 860-861. · Zbl 0938.68074
[88] Berry, A.; Bordat, J.-P.; Heggernes, P.; Simonet, G.; Villanger, Y., A wide-range algorithm for minimal triangulation from an arbitrary ordering, J. algorithm, 58, 33-66, (2006) · Zbl 1093.68137
[89] Dahlhaus, E., Minimal elimination ordering inside a given chordal graph, (), 132-143 · Zbl 0886.05103
[90] Heggernes, P.; Villanger, Y., Efficient implementation of a minimal triangulation algorithm, (), 550-561 · Zbl 1019.68809
[91] Berry, A.; Heggernes, P.; Villanger, Y., A vertex incremental approach for maintaining chordality, Disc. math., 306, 318-336, (2006) · Zbl 1087.05054
[92] Peyton, B.W., Minimal orderings revisited, SIAM J. matrix anal. appl., 23, 271-294, (2001) · Zbl 1044.65035
[93] Heggernes, P., Minimal triangulations of graphs: a survey, Disc. math., 306, 297-317, (2006) · Zbl 1086.05069
[94] Heggernes, P.; Telle, J.A.; Villanger, Y., Computing minimal triangulations in time \(O(n^\alpha \log n) = o(n^{2.376})\), SIAM J. disc. math., 19, 900-913, (2005) · Zbl 1105.05066
[95] J.G. Siek, L.-Q. Lee, A. Lumsdaine, The Boost Graph Library: User Guide and Reference Manual, Addison-Wesley Professional, Reading, MA, 2001. Software available on: <http://www.boost.org>.
[96] Shoikhet, K.; Geiger, D., A practical algorithm for finding optimal triangulations, (), 185-190
[97] Bodlaender, H.L.; Koster, A.M.C.A.; Wolle, T., Contraction and treewidth lower bounds, J. graph algorithm appl., 10, 5-49, (2006) · Zbl 1161.68644
[98] Treewidthlib, 2004. Available from: <http://www.cs.uu.nl/people/hansb/treewidthlib>.
[99] The second DIMACS implementation challenge: NP-Hard Problems: Maximum Clique, Graph Coloring, and Satisfiability, 1992-1993. See: <http://dimacs.rutgers.edu/Challenges/>.
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.