On treewidth approximations. (English) Zbl 1035.05087

Summary: We introduce a natural heuristic for approximating the treewidth of graphs. We prove that this heuristic gives a constant factor approximation for the treewidth of graphs with bounded asteroidal number. Using a different technique, we give a \(\mathcal O(\log k)\) approximation algorithm for the treewidth of arbitrary graphs, where \(k\) is the treewidth of the input graph.


05C85 Graph algorithms (graph-theoretic aspects)
68W25 Approximation algorithms
Full Text: DOI


[1] Ahuja, R.K.; Magnanti, T.L.; Orlin, J.B., Network flows: theory, algorithms, and applications, (1993), Prentice Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2] E. Amir, Efficient approximation for triangulation of minimum treewidth, in Proceedings of the 17th Conference on Uncertainty in Artificial Intelligence (UAI ’01), 2001. http://www.cs.berkeley.edu/ eyal/papers/decomp-uai01.ps.
[3] A. Berry, Désarticulation d’un graphe, Ph.D. Thesis, Université Montpellier II, 1998.
[4] Bodlaender, H.; Gilbert, J.R.; Hafsteinsson, H.; Kloks, T., Approximating treewidth, pathwidth, frontsize and shortest elimination tree, J. algorithms, 18, 238-255, (1995) · Zbl 0818.68118
[5] V. Bouchitté, I. Todinca, Approximating the treewidth of AT-free graphs, in Proceedings of the 26th Workshop on Graph-Theoretic Aspects in Computer Science (WG 2000), Lecture Notes in Computer Sciences, Vol. 1928, Springer, Berlin, 2000, pp. 59-70. · Zbl 0988.68124
[6] Bouchitté, V.; Todinca, I., Treewidth and minimum fill-ingrouping the minimal separators, SIAM J. comput., 31, 1, 212-232, (2001) · Zbl 0987.05085
[7] Bouchitté, V.; Todinca, I., Listing all potential maximal cliques of a graph, Theoret. comput. sci., 276, 1-2, 17-32, (2002) · Zbl 1002.68104
[8] Broersma, H.; Kloks, T.; Kratsch, D.; Müller, H., A generalization of AT-free graphs and a generic algorithm for solving triangulation problems, Algorithmica, 32, 594-610, (2002) · Zbl 1009.68099
[9] Even, G.; Naor, J.; Rao, S.; Schieber, B., Fast approximate graph partitioning algorithms, SIAM J. comput., 28, 6, 2187-2214, (1999) · Zbl 0936.68109
[10] H.N. Gabow, Using expander graphs to find vertex connectivity, in 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA. IEEE Computer Society, 2000, pp. 410-420.
[11] Kloks, T.; Kratsch, D., Listing all minimal separators of a graph, SIAM J. comput., 27, 3, 605-613, (1998) · Zbl 0907.68136
[12] Kloks, T.; Kratsch, D.; Müller, H., Approximating the bandwidth for asteroidal triple-free graphs, J. algorithms, 32, 41-57, (1999) · Zbl 0951.68113
[13] Kloks, T.; Kratsch, D.; Müller, H., On the structure of graphs with bounded asteroidal number, Graphs combin., 17, 295-306, (2001) · Zbl 0989.05059
[14] Leighton, T.; Rao, S., Multicommodity MAX-flow MIN-cut theorems and their use in designing approximation algorithms, J. ACM, 46, 6, 787-832, (1999) · Zbl 1065.68666
[15] Parra, A.; Scheffler, P., Characterizations and algorithmic applications of chordal graph embeddings, Discrete appl. math., 79, 1-3, 171-188, (1997) · Zbl 0887.05044
[16] Tarjan, R.E., Decomposition by clique separators, Discrete math., 55, 221-232, (1985) · Zbl 0572.05039
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.