## Treewidth computations. II. Lower bounds.(English)Zbl 1220.68071

Summary: For several 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. Good lower bounds on the treewidth of a graph can, amongst others, help to speed up branch and bound algorithms that compute the treewidth of a graph exactly. A high lower bound for a specific graph instance can tell that a dynamic programming approach for solving a problem is infeasible for this instance. This paper gives an overview of several recent methods that give lower bounds on the treewidth of graphs.
For a review of Part I see ibid. 208, No. 3, 259–275 (2010; Zbl 1186.68328).

### MSC:

 68R10 Graph theory (including graph drawing) in computer science 05C05 Trees 05C51 Graph designs and isomorphic decomposition 05C85 Graph algorithms (graph-theoretic aspects)

### Keywords:

treewidth; lower bounds; heuristics; graph algorithms

Zbl 1186.68328

### Software:

Treewidthlib; DIMACS; BGL; ComputeTW; Boost
Full Text:

### References:

 [1] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows: theory, algorithms, and applications, (1993), Prentice Hall Upper Saddle River, NJ, USA · Zbl 1201.90001 [2] Arnborg, S., Efficient algorithms for combinatorial problems on graphs with bounded decomposability - A survey, Bit, 25, 2-23, (1985) · Zbl 0573.68018 [3] Arnborg, S.; Proskurowski, A., Characterization and recognition of partial 3-trees, SIAM journal on algebraic and discrete methods, 7, 305-314, (1986) · Zbl 0597.05027 [4] Bellenbaum, P.; Diestel, R., Two short proofs concerning tree-decompositions, Combinatorics, probability, and computing, 11, 541-547, (2002) · Zbl 1018.05081 [5] Bodlaender, H.L., A linear time algorithm for finding tree-decompositions of small treewidth, SIAM journal on computing, 25, 1305-1317, (1996) · Zbl 0864.68074 [6] Bodlaender, H.L., A partial k-arboretum of graphs with bounded treewidth, Theoretical computer science, 209, 1-45, (1998) · Zbl 0912.68148 [7] Bodlaender, H.L., Necessary edges in k-chordalizations of graphs, Journal of combinatorial optimization, 7, 283-290, (2003) · Zbl 1031.05120 [8] 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 [9] Bodlaender, H.L.; Grigoriev, A.; Koster, A.M.C.A., Treewidth lower bounds with brambles, Algorithmica, 51, 81-98, (2008) · Zbl 1138.68065 [10] Bodlaender, H.L.; Kloks, T.; Kratsch, D., Treewidth and pathwidth of permutation graphs, SIAM journal on discrete mathematics, 8, 4, 606-616, (1995) · Zbl 0840.05087 [11] Bodlaender, H.L.; Koster, A.M.C.A., On the maximum cardinality search lower bound for treewidth, Discrete applied mathematics, 155, 11, 1348-1372, (2007) · Zbl 1119.05101 [12] Bodlaender, H.L.; Koster, A.M.C.A., Treewidth computations I. upper bounds, Information and computation, 208, 259-275, (2010) · Zbl 1186.68328 [13] H.L. Bodlaender, A.M.C.A. Koster, Treewidth computations III. Exact algorithms and preprocessing, in preparation. [14] Bodlaender, H.L.; Koster, A.M.C.A.; Eijkhof, F.v.d., Pre-processing rules for triangulation of probabilistic networks, Computational intelligence, 21, 3, 286-305, (2005) [15] H.L. Bodlaender, T. Wolle, Contraction degeneracy on cographs, Technical Report UU-CS-2004-031, Institute for Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands, 2004. [16] Bodlaender, H.L.; Wolle, T.; Koster, A.M.C.A., Contraction and treewidth lower bounds, Journal of graph algorithms and applications, 10, 5-49, (2006) · Zbl 1161.68644 [17] Clautiaux, F.; Carlier, J.; Moukrim, A.; Négre, S., New lower and upper bounds for graph treewidth, (), 70-80 · Zbl 1023.68645 [18] Cole Smith, J.; Ulusal, E.; Hicks, I.V., A combinatorial optimization algorithm for solving the branchwidth problem, Technical Report, Rice University, 2010; URL: · Zbl 1241.90121 [19] Diestel, R., Graph theory, (2010), Springer-Verlag · Zbl 1204.05001 [20] The second DIMACS implementation challenge, NP-hard problems: maximum clique, graph coloring, and satisfiability, (1992/1993), see [21] Gogate, V.; Dechter, R., A complete anytime algorithm for treewidth, (), 201-208 [22] Hicks, I.V., Planar branch decompositions I: the ratcatcher, INFORMS journal on computing, 17, 402-412, (2005) · Zbl 1239.05176 [23] Hicks, I.V.; Koster, A.M.C.A.; Kolotoğlu, E., Branch and tree decomposition techniques for discrete optimization, (), 1-29, Chapter 1 [24] Koster, A.M.C.A., Computetw - an interactive platform for computing treewidth of graphs, (2009) [25] Koster, A.M.C.A.; Wolle, T.; Bodlaender, H.L., Degree-based treewidth lower bounds, (), 101-112 · Zbl 1121.68346 [26] B. Lucena, Dynamic programming, tree-width, and computation on graphical models, PhD thesis, Brown University, Providence, RI, USA, 2002. [27] Lucena, B., A new lower bound for tree-width using maximum cardinality search, SIAM journal on discrete mathematics, 16, 345-353, (2003) · Zbl 1041.68071 [28] Markov, I.L.; Shi, Y., Constant-degree graph expansions that preserve treewidth, Algorithmica, 59, 461-470, (2011) · Zbl 1215.68186 [29] S. Ramachandramurthi, Algorithms for VLSI layout based on graph width metrics, PhD thesis, Computer Science Department, University of Tennessee, Knoxville, Tennessee, USA, 1994. [30] Ramachandramurthi, S., A lower bound for treewidth and its consequences, (), 14-25 [31] Ramachandramurthi, S., The structure and number of obstructions to treewidth, SIAM journal on discrete mathematics, 10, 146-157, (1997) · Zbl 0869.05060 [32] Reed, B.A., Tree width and tangles, a new measure of connectivity and some applications, (), 87-162 · Zbl 0895.05034 [33] Robertson, N.; Seymour, P.D., Graph minors. II. algorithmic aspects of tree-width, Journal of algorithms, 7, 309-322, (1986) · Zbl 0611.05017 [34] H. Röhrig, Tree decomposition: A feasibility study, Masterʼs thesis, Max-Planck-Institut für Informatik, Saarbrücken, Germany, 1998. [35] Schrijver, A., Combinatorial optimization. polyhedra and efficiency, (2003), Springer Berlin · Zbl 1041.90001 [36] Seymour, P.D.; Thomas, R., Graph searching and a minimax theorem for tree-width, Journal of combinatorial theory, series B, 58, 239-257, (1993) [37] Seymour, P.D.; Thomas, R., Call routing and the ratcatcher, Combinatorica, 14, 2, 217-241, (1994) · Zbl 0799.05057 [38] Shoikhet, K.; Geiger, D., A practical algorithm for finding optimal triangulations, (), 185-190 [39] Siek, J.G.; Lee, L.-Q.; Lumsdaine, A., The boost graph library: user guide and reference manual, (2001), Addison-Wesley Professional, Software available on [40] Sunil Chandran, L.; Sivadasan, N., Boxicity and treewidth, Journal of combinatorial theory, series B, 97, 733-744, (2007) · Zbl 1121.05091 [41] Sunil Chandran, L.; Subramanian, C.R., A spectral lower bound for the treewidth of a graph and its consequences, Information processing letters, 87, 195-200, (2003) · Zbl 1161.68647 [42] Sunil Chandran, L.; Subramanian, C.R., Girth and treewidth, Journal of combinatorial theory, series B, 93, 23-32, (2005) · Zbl 1064.05084 [43] Tarjan, R.E.; Yannakakis, M., Simple linear time algorithms to test chordiality of graphs, test acyclicity of graphs, and selectively reduce acyclic hypergraphs, SIAM journal on computing, 13, 566-579, (1984) · Zbl 0545.68062 [44] TreewidthLIB, (2004) [45] West, D.B., Introduction to graph theory, (2001), Prentice Hall [46] T. Wolle, Computational aspects of treewidth. Lower bounds and network reliability, PhD thesis, Faculty of Science, Utrecht University, Utrecht, the Netherlands, 2005. [47] T. Wolle, H.L. Bodlaender, A note on edge contraction, Technical Report UU-CS-2004-028, Institute of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands, 2004. [48] T. Wolle, A.M.C.A. Koster, H.L. Bodlaender, A note on contraction degeneracy, Technical Report UU-CS-2004-042, Institute of Information and Computing Sciences, Utrecht University, Utrecht, The Netherlands, 2004. · Zbl 1111.68558
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.