Abstract
This paper presents algorithms whose input is an undirected graph, and whose output is a tree decomposition of width that approximates the optimal, the treewidth of that graph. The algorithms differ in their computation time and their approximation guarantees. The first algorithm works in polynomial-time and finds a factor-O(log OPT) approximation, where OPT is the treewidth of the graph. This is the first polynomial-time algorithm that approximates the optimal by a factor that does not depend on n, the number of nodes in the input graph. As a result, we get an algorithm for finding pathwidth within a factor of O(log OPT⋅log n) from the optimal. We also present algorithms that approximate the treewidth of a graph by constant factors of 3.66, 4, and 4.5, respectively and take time that is exponential in the treewidth. These are more efficient than previously known algorithms by an exponential factor, and are of practical interest. Finding triangulations of minimum treewidth for graphs is central to many problems in computer science. Real-world problems in artificial intelligence, VLSI design and databases are efficiently solvable if we have an efficient approximation algorithm for them. Many of those applications rely on weighted graphs. We extend our results to weighted graphs and weighted treewidth, showing similar approximation results for this more general notion. We report on experimental results confirming the effectiveness of our algorithms for large graphs associated with real-world problems.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abrahamson, K.A., Fellows, M.R.: Finite automata, bounded treewidth and well-quasiordering. In: Graph Structure Theory, Proc. Conf. on Graph Minors (Seattle, 1991). Contemporary Mathematics, vol. 147, pp. 539–564. American Mathematical Society, Providence (1993)
Amir, E.: Partitioning and reasoning project website. http://www.cs.uiuc.edu/~eyal/decomp
Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: 17th Conference on Uncertainty in Artificial Intelligence (UAI ’01) (2001)
Amir, E., Krauthgamer, R., Rao, S.: Constant factor approximation of vertex-cuts in planar graphs. In: Proc. 35rd ACM Symp. on Theory of Computing, pp. 90–99. ACM, New York (2003)
Amir, E., McIlraith, S.: Partition-based logical reasoning. In: Principles of Knowledge Representation and Reasoning: Proc. Seventh Int’l Conference (KR ’2000), pp. 389–400. Kaufmann, Los Altos (2000)
Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a K-tree. SIAM J. Algebr. Discrete Methods 8, 277–284 (1987)
Arnborg, S., Lagergren, J., Seese, D.: Problems easy for tree-decomposable graphs. J. Algorithms 12, 308–340 (1991)
Becker, A., Geiger, D.: A sufficiently fast algorithm for finding close to optimal junction trees. In: Proc. Twelfth Conference on Uncertainty in Artificial Intelligence (UAI ’96), pp. 81–89. Kaufmann, Los Altos (1996)
Becker, A., Geiger, D.: A sufficiently fast algorithm for finding close to optimal clique trees. Artif. Intell. 125(1–2), 3–17 (2001)
Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996)
Bodlaender, H.L.: Treewidth: Algorithmic techniques and results. In: Prívara, I., Ruzicka, P. (eds.) Mathematical Foundations of Computer Science 1997. LNCS, vol. 1295, pp. 19–36. Springer, Berlin (1997)
Bodlaender, H.L.: Personal communication (September 2000)
Bodlaender, H.L., Gilbert, J.R., Hafsteinsson, H., Kloks, T.: Approximating treewidth, pathwidth, frontsize, and shortest elimination tree. J. Algorithms 18(2), 238–255 (1995)
Bodlaender, H.L., Kloks, T.: Better algorithms for the pathwidth and treewidth of graphs. In: Automata, Languages and Programming, 18th International Colloquium. LNCS, vol. 510, pp. 544–555. Springer, Berlin (1991)
Bouchitte, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212–232 (2001)
Broersma, H., Kloks, T., Kratsch, D., Müller, H.: A generalization of AT-free graphs and a generic algorithm for solving treewidth, minimum fill-in and vertex ranking. In: WG: Graph-Theoretic Concepts in Computer Science, International Workshop WG. LNCS, vol. 1517, pp. 88–99. Springer, Berlin (1998)
Cherkassky, B.V., Goldberg, A.V.: On implementing the push-relabel method for the maximum flow problem. Algorithmica 19(4), 390–410 (1997)
Cohen, P., Chaudhri, V., Pease, A., Schrag, R.: Does prior knowledge facilitate the development of knowledge-based systems. In: Proc. National Conference on Artificial Intelligence (AAAI ’99), pp. 221–226. AAAI Press, Menlo Park (1999)
Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. McGraw–Hill, New York (1989)
Cunningham, W.H.: The optimal multiterminal cut problem. In: DIMACS Series in Disc. Math. and Theor. Comput. Sci., vol. 5, pp. 105–120. American Mathematical Society, Providence (1991)
Dechter, R.: Bucket elimination: A unifying framework for probabilistic inference. In: Proc. Twelfth Conference on Uncertainty in Artificial Intelligence (UAI ’96), pp. 211–219. Kaufmann, Los Altos (1996)
Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artif. Intell. 38, 353–366 (1989)
Demaine, E.D., Hajiaghayi, M.T., Nishimura, N., Ragde, P., Thilikos, D.M.: Approximation algorithms for classes of graphs excluding single-crossing graphs as minors. J. Comput. Syst. Sci. 69(2), 166–195 (2004)
Dinic, E.A.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Sov. Math. Dokl. 11, 1277–1280 (1970)
Even, S.: An algorithm for determining whether the connectivity of a graph is at least k. SIAM J. Comput. 4(3), 393–396 (1975)
Even, S.: Graph Algorithms. Computer Science Press, New York (1979)
Feige, U., Hajiaghayi, M.T., Lee, J.R.: Improved approximation algorithms for minimum-weight vertex separators. In: Proc. 37rd ACM Symp. on Theory of Computing, pp. 563–572. ACM, New York (2005)
Fomin, F.V., Kratsch, D., Todinca, I.: Exact (exponential) algorithms for treewidth and minimum fill-in. In: Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP 2004), pp. 568–580. Springer, Berlin (2004)
Ford, L.R. Jr., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)
Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in directed and node weighted graphs. In: Automata, Languages and Programming, 21st ICALP. LNCS, vol. 820, pp. 487–498. Springer, Berlin (1994)
Goldman, R., Shivakumar, N., Venkatasubramanian, S., Garcia-Molina, H.: Proximity search in databases. In: Proceedings of the 24th Intl’ Conf. on Very Large Databases (VLDB 1998) (1998)
Hoos, H.H., Stützle, T.: SATLIB—the satisfiability library. Canadian SATLIB site, hostet by the Laboratory for Computational Intelligence at the computer science department of the University of British Columbia in Vancouver, Canada, 2001. Can be found at http://www.satlib.org
Jensen, F.V., Lauritzen, S.L., Olesen, K.G.: Bayesian updating in recursive graphical models by local computation. Comput. Stat. Q. 4, 269–282 (1990)
Kjaerulff, U.: Aspects of efficiency improvement in Bayesian networks. PhD thesis, Aalborg University, Department of Mathematics and Computer Science, Fredrik Bajers Vej 7E, DK-9220 Aalborg, Denmark (1993)
Klein, P., Agrawal, A., Ravi, R., Rao, S.: Approximation through multicommodity flow. In: Proc. 31st IEEE Symp. on Foundations of Computer Science (FOCS’90), pp. 726–739. IEEE Press, New York (1990)
Kloks, T.: In: Treewidth: computations and approximations. LNCS, vol. 842. Springer, Berlin (1994)
Lagergren, J.: Efficient parallel algorithms for tree-decomposition and related problems. In: Proc. 31st IEEE Symp. on Foundations of Computer Science (FOCS’90), pp. 173–182. IEEE Press, New York (1990)
Lagergren, J., Arnborg, S.: Finding minimal forbidden minors using a finite congruence. In: Proc. 18th Int. Coll. Automata, Languages and Programming. LNCS, vol. 510, pp. 532–543. Springer, Berlin (1991)
Lauritzen, S.L., Spiegelhalter, D.J.: Local computations with probabilities on graphical structures and their application to expert systems. J. R. Stat. Soc. B 50(2), 157–224 (1988)
Leighton, T., Makedon, F., Plotkin, S., Stein, C., Tardos, E., Tragoudas, S.: Fast approximation algorithms for multicommodity flow problems. J. Comput. Syst. Sci. 50(2), 228–243 (1995)
Leighton, T., Rao, S.: An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In: Proc. 29th IEEE Symp. on Foundations of Computer Science (FOCS’88), pp. 422–431 (1988)
Leighton, T., Rao, S.: Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms. J. ACM 46(6), 787–832 (1999)
Lenat, D.B.: Cyc: A large-scale investment in knowledge infrastructure. Commun. ACM 38(11), 33–38 (1995)
MacCartney, B., McIlraith, S., Amir, E., Uribe, T.: Practical partition-based theorem proving for large knowledge bases. In: Proc. Eighteenth International Joint Conference on Artificial Intelligence (IJCAI ’03), pp. 89–96. Kaufmann, Los Altos (2003)
McIlraith, S., Amir, E.: Theorem proving with structured theories. In: Proc. Seventeenth International Joint Conference on Artificial Intelligence (IJCAI ’01), pp. 624–631. Kaufmann, Los Altos (2001)
Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Kaufmann, Los Altos (1988)
Pradhan, M., Provan, G., Middleton, B., Henrion, M.: Knowledge engineering for large belief networks. In: Proc. Tenth Conference on Uncertainty in Artificial Intelligence (UAI ’94), pp. 484–490. Kaufmann, Los Altos (1994)
Reed, B.A.: Finding approximate separators and computing tree width quickly. In: Proc. 24th ACM Symp. on Theory of Computing, pp. 221–228. ACM, New York (1992)
Robertson, N., Seymour, P.D.: Graph minors. II: Algorithmic aspects of treewidth. J. Algorithms 7, 309–322 (1986)
Robertson, N., Seymour, P.D.: Graph minors XIII. the disjoint paths problem. J. Comb. Theory Ser. B 63, 65–110 (1995)
Rose, D.J.: Triangulated graphs and the elimination process. J. Discrete Math. 7, 317–322 (1974)
Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217–241 (1994)
Shoikhet, K., Geiger, D.: A practical algorithm for finding optimal triangulations. In: Proc. National Conference on Artificial Intelligence (AAAI ’97), pp. 185–190. Kaufmann, Los Altos (1997)
Walter, J.R.: Representations of chordal graphs as subtrees of a tree. J. Graph Theory 2, 265–267 (1978)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Amir, E. Approximation Algorithms for Treewidth. Algorithmica 56, 448–479 (2010). https://doi.org/10.1007/s00453-008-9180-4
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-008-9180-4