×

zbMATH — the first resource for mathematics

Approximation algorithms for treewidth. (English) Zbl 1187.68703
Summary: 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\cdot \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.

MSC:
68W25 Approximation algorithms
68R10 Graph theory (including graph drawing) in computer science
68M99 Computer system organization
Software:
SATLIB
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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) · Zbl 0791.05094
[2] Amir, E.: Partitioning and reasoning project website. http://www.cs.uiuc.edu/\(\sim\)eyal/decomp
[3] Amir, E.: Efficient approximation for triangulation of minimum treewidth. In: 17th Conference on Uncertainty in Artificial Intelligence (UAI ’01) (2001)
[4] 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) · Zbl 1192.68867
[5] 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) · Zbl 0989.68525
[6] Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a K-tree. SIAM J. Algebr. Discrete Methods 8, 277–284 (1987) · Zbl 0611.05022 · doi:10.1137/0608024
[7] Arnborg, S., Lagergren, J., Seese, D.: Problems easy for tree-decomposable graphs. J. Algorithms 12, 308–340 (1991) · Zbl 0734.68073 · doi:10.1016/0196-6774(91)90006-K
[8] 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)
[9] Becker, A., Geiger, D.: A sufficiently fast algorithm for finding close to optimal clique trees. Artif. Intell. 125(1–2), 3–17 (2001) · Zbl 0972.68152 · doi:10.1016/S0004-3702(00)00075-8
[10] Bodlaender, H.L.: A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM J. Comput. 25(6), 1305–1317 (1996) · Zbl 0864.68074 · doi:10.1137/S0097539793251219
[11] 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) · Zbl 0941.05057
[12] Bodlaender, H.L.: Personal communication (September 2000)
[13] 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) · Zbl 0818.68118 · doi:10.1006/jagm.1995.1009
[14] 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) · Zbl 0764.68108
[15] Bouchitte, V., Todinca, I.: Treewidth and minimum fill-in: grouping the minimal separators. SIAM J. Comput. 31(1), 212–232 (2001) · Zbl 0987.05085 · doi:10.1137/S0097539799359683
[16] 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) · Zbl 0928.68086
[17] Cherkassky, B.V., Goldberg, A.V.: On implementing the push-relabel method for the maximum flow problem. Algorithmica 19(4), 390–410 (1997) · Zbl 0898.68029 · doi:10.1007/PL00009180
[18] 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)
[19] Cormen, T.H., Leiserson, C.E., Rivest, R.L.: Introduction to Algorithms. McGraw–Hill, New York (1989) · Zbl 1187.68679
[20] 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) · Zbl 0821.90125
[21] 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)
[22] Dechter, R., Pearl, J.: Tree clustering for constraint networks. Artif. Intell. 38, 353–366 (1989) · Zbl 0665.68084 · doi:10.1016/0004-3702(89)90037-4
[23] 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) · Zbl 1073.68063 · doi:10.1016/j.jcss.2003.12.001
[24] Dinic, E.A.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Sov. Math. Dokl. 11, 1277–1280 (1970) · Zbl 0219.90046
[25] Even, S.: An algorithm for determining whether the connectivity of a graph is at least k. SIAM J. Comput. 4(3), 393–396 (1975) · Zbl 0311.05133 · doi:10.1137/0204034
[26] Even, S.: Graph Algorithms. Computer Science Press, New York (1979) · Zbl 0441.68072
[27] 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) · Zbl 1192.68893
[28] 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) · Zbl 1099.68076
[29] Ford, L.R. Jr., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962) · Zbl 0106.34802
[30] 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) · Zbl 1068.68178
[31] 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)
[32] 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
[33] 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) · Zbl 0715.68076
[34] 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)
[35] 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)
[36] Kloks, T.: In: Treewidth: computations and approximations. LNCS, vol. 842. Springer, Berlin (1994) · Zbl 0825.68144
[37] 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)
[38] 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) · Zbl 0764.68122
[39] 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) · Zbl 0684.68106
[40] 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) · Zbl 0826.68055 · doi:10.1006/jcss.1995.1020
[41] 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)
[42] 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 · doi:10.1145/331524.331526
[43] Lenat, D.B.: Cyc: A large-scale investment in knowledge infrastructure. Commun. ACM 38(11), 33–38 (1995) · Zbl 01936346 · doi:10.1145/219717.219745
[44] 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)
[45] 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) · Zbl 0990.90558
[46] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Kaufmann, Los Altos (1988) · Zbl 0746.68089
[47] 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)
[48] 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)
[49] Robertson, N., Seymour, P.D.: Graph minors. II: Algorithmic aspects of treewidth. J. Algorithms 7, 309–322 (1986) · Zbl 0611.05017 · doi:10.1016/0196-6774(86)90023-4
[50] Robertson, N., Seymour, P.D.: Graph minors XIII. the disjoint paths problem. J. Comb. Theory Ser. B 63, 65–110 (1995) · Zbl 0823.05038 · doi:10.1006/jctb.1995.1006
[51] Rose, D.J.: Triangulated graphs and the elimination process. J. Discrete Math. 7, 317–322 (1974) · Zbl 0285.05128 · doi:10.1016/0012-365X(74)90042-9
[52] Seymour, P.D., Thomas, R.: Call routing and the ratcatcher. Combinatorica 14(2), 217–241 (1994) · Zbl 0799.05057 · doi:10.1007/BF01215352
[53] 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)
[54] Walter, J.R.: Representations of chordal graphs as subtrees of a tree. J. Graph Theory 2, 265–267 (1978) · Zbl 0441.05022 · doi:10.1002/jgt.3190020311
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.