Improved approximation algorithms for minimum-weight vertex separators

ABSTRACT

We develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L1 (and even Euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes.We obtain an O(√log n) approximation for min-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be Θ(√log n). We also prove various approximate max-flow/min-vertex-cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded-minor family of graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best-known ratio was O(log n).These results have a number of applications. We exhibit an O(√log n) pseudo-approximation for finding balanced vertex separators in general graphs. In fact, we achieve an approximation ratio of O(√log opt) where opt is the size of an optimal separator, improving over the previous best bound of O(log opt). Likewise, we obtain improved approximation ratios for treewidth: In any graph of treewidth k, we show how to find a tree decomposition of width at most O(k √log k), whereas previous algorithms yielded O(k log k). For graphs excluding a fixed graph as a minor (which includes, e.g., bounded genus graphs), we give a constant-factor approximation for the treewidth; this can be used to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs.

REFERENCES

• 1: N. Alon, P. Seymour, and R. Thomas, A separator theorem for nonplanar graphs, J. Amer. Math. Soc., 3 (1990), pp. 801--808.
• 2: Eyal Amir, Efficient Approximation for Triangulation of Minimum Treewidth, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.7-15, August 02-05, 2001
• 3: Eyal Amir , Robert Krauthgamer , Satish Rao, Constant factor approximation of vertex-cuts in planar graphs, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780557]
• 4: S. Arora, J. R. Lee, and A. Naor, Euclidean distortion and the Sparsest Cut. Manuscript, 2004.
• 5: Sanjeev Arora , Satish Rao , Umesh Vazirani, Expander flows, geometric embeddings and graph partitioning, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.222-231, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007355]
• 6: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 7: S. N. Bhatt and F. T. Leighton, A framework for solving VLSI graph layout problems, J. Comput. System Sci., 28 (1984), pp. 300--343.
• 8: Hans L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, v.209 n.1-2, p.1-45, Dec. 6, 1998 [doi>10.1016/S0304-3975(97)00228-4 ]
• 9: Hans L. Bodlaender , John R. Gilbert , Hjálmtýr Hafsteinsson , Ton Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, Journal of Algorithms, v.18 n.2, p.238-255, March 1995 [doi>10.1006/jagm.1995.1009 ]
• 10: V. Bouchitté, D. Kratsch, H. Müller, and I. Todinca, On treewidth approximations, in Proceedings of the 1st Cologne-Twente Workshop on Graphs and Combinatorial Optimization, vol. 8 of Electronic Notes in Discrete Mathematics, 2001.
• 11: Vincent Bouchitté , Ioan Todinca, Treewidth and Minimum Fill-in: Grouping the Minimal Separators, SIAM Journal on Computing, v.31 n.1, p.212-232, 2001 [doi>10.1137/S0097539799359683]
• 12: J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math., 52 (1985), pp. 46--52.
• 13: Thang Nguyen Bui , Curt Jones, Finding good approximate vertex and edge partitions is NP-hard, Information Processing Letters, v.42 n.3, p.153-159, May 25, 1992 [doi>10.1016/0020-0190(92)90140-Q ]
• 14: Shuchi Chawla , Anupam Gupta , Harald Räcke, Embeddings of negative-type metrics and an improved approximation to generalized sparsest cut, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 15: Erik D. Demaine , MohammadTaghi Hajiaghayi, Bidimensionality: new connections between FPT algorithms and PTASs, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: Erik D. Demaine , MohammadTaghi Hajiaghayi, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 17: Erik D. Demaine , Mohammad Taghi Hajiaghayi , Naomi Nishimura , Prabhakar Ragde , Dimitrios M. Thilikos, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences, v.69 n.2, p.166-166, September 2004 [doi>10.1016/j.jcss.2003.12.001]
• 18: Guy Even , Joseph Seffi Naor , Satish Rao , Baruch Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), v.47 n.4, p.585-616, July 2000 [doi>10.1145/347476.347478]
• 19: G. Even, J. Naor, B. Schieber, and M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20 (1998), pp. 151--174.
• 20: Uriel Feige, Relations between average case complexity and approximation complexity, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509985]
• 21: U. Feige and S. Kogan, Hardness of approximation of the balanced complete bipartite subgraph problem, Technical report MCS04-04, Department of Computer Science and Applied Math., The Weizmann Institute of Science, (2004).
• 22: Uriel Feige , Gideon Schechtman, On the optimality of the random hyperplane rounding technique for max cut, Random Structures & Algorithms, v.20 n.3, p.403-440, May 2002 [doi>10.1002/rsa.10036 ]
• 23: John R. Gilbert , Joan P. Hutchinson , Robert Endre Tarjan, A separator theorem for graphs of bounded genus, Journal of Algorithms, v.5 n.3, p.391-407, Sept. 1984 [doi>10.1016/0196-6774(84)90019-1]
• 24: Martin Grohe, Local Tree-Width, Excluded Minors, and Approximation Algorithms, Combinatorica, v.23 n.4, p.613-632, December 2003 [doi>10.1007/s00493-003-0037-9]
• 25: L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combinatorial Theory, 1 (1966), pp. 385--393.
• 26: Jonathan A. Kelner, Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, p.455-464, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007357]
• 27: Subhash Khot, Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.136-145, October 17-19, 2004 [doi>10.1109/FOCS.2004.59]
• 28: S. Khot and N. Vishnoi, On embeddability of negative type metrics into l1. Manuscript, 2004.
• 29: Philip Klein , Serge A. Plotkin , Satish Rao, Excluded minors, network decomposition, and multicommodity flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.682-690, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167261]
• 30: Robert Krauthgamer , James R. Lee , Manor Mendel , Assaf Naor, Measured Descent: A New Embedding Method for Finite Metrics, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), p.434-443, October 17-19, 2004 [doi>10.1109/FOCS.2004.41]
• 31: E. L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976.
• 32: James R. Lee, On distance scales, embeddings, and efficient relaxations of the cut cone, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 33: Frank Thomson Leighton, Complexity issues in VLSI: optimal layouts for the shuffle-exchange graph and other networks, MIT Press, Cambridge, MA, 1983
• 34: Tom Leighton , Satish Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, Journal of the ACM (JACM), v.46 n.6, p.787-832, Nov. 1999 [doi>10.1145/331524.331526]
• 35: C. Leiserson, Area-efficient graph layouts (for VLSI), in 21th Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., Los Alamitos, CA, 1980, pp. 270--280.
• 36: N. Linial, E. London, and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15 (1995), pp. 215--245.
• 37: R. J. Lipton and R. E. Tarjan, Applications of a planar separator theorem, SIAM J. Comput., 9 (1980), pp. 615--627.
• 38: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, Journal of the ACM (JACM), v.44 n.1, p.1-29, Jan. 1997 [doi>10.1145/256292.256294]
• 39: Gary L. Miller , Shang-Hua Teng , William Thurston , Stephen A. Vavasis, Geometric Separators for Finite-Element Meshes, SIAM Journal on Scientific Computing, v.19 n.2, p.364-386, March 1998 [doi>10.1137/S1064827594262613]
• 40: Yuri Rabinovich, On average distortion of embedding metrics into the line and into L₁, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780609]
• 41: Satish Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, Proceedings of the fifteenth annual symposium on Computational geometry, p.300-306, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304983]
• 42: N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7 (1986), pp. 309--322.
• 43: Neil Robertson , P. D. Seymour, Graph minors: X. obstructions to tree-decomposition, Journal of Combinatorial Theory Series B, v.52 n.2, p.153-190, July 1991 [doi>10.1016/0095-8956(91)90061-N]
• 44: P. D. Seymour and R. Thomas, Call routing and the ratcatcher, Combinatorica, 14 (1994), pp. 217--241.
• 45: D. B. West, Introduction to Graph Theory, Prentice Hall Inc., Upper Saddle River, NJ, 1996.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms, Theory

Keywords:
approximation algorithms, metric embeddings, semidefinite programming, treewidth, vertex separators