Article

Improved approximation algorithms for minimum-weight vertex separators

Authors:

MohammadTaghi Hajiaghayi,

James R. LeeAuthors Info & Claims

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

Pages 563 - 572

https://doi.org/10.1145/1060590.1060674

Published: 22 May 2005 Publication History

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 L₁ (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]

E. Amir, Efficient approximation for triangulation of minimum treewidth, in Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann, 2001, pp. 7--15. Journal version titled "Approximation Algorithms for Treewidth" is available at the author's homepage.

Digital Library

[3]

E. Amir, R. Krauthgamer, and S. Rao, Constant factor approximation of vertex-cuts in planar graphs, in Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, ACM Press, 2003, pp. 90--99.

Digital Library

[4]

S. Arora, J. R. Lee, and A. Naor, Euclidean distortion and the Sparsest Cut. Manuscript, 2004.

[5]

S. Arora, S. Rao, and U. Vazirani, Expander flows, geometric embeddings, and graph partitionings, in 36th Annual Symposium on the Theory of Computing, 2004.

Digital Library

[6]

Y. Aumann and Y. Rabani, An O(log k) approximate min-cut max-flow theorem and approximation algorithm, SIAM J. Comput., 27 (1998), pp. 291--301 (electronic).

Digital Library

[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]

H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci., 209 (1998), pp. 1--45.

Digital Library

[9]

H. L. Bodlaender, J. R. Gilbert, H. Hafsteinsson, and T. Kloks, Approximating treewidth, pathwidth, frontsize, and shortest elimination tree, J. Algorithms, 18 (1995), pp. 238--255.

Digital Library

[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]

V. Bouchitté and I. Todinca, Treewidth and minimum fill-in: grouping the minimal separators, SIAM J. Comput., 31 (2001), pp. 212--232.

Digital Library

[12]

J. Bourgain, On Lipschitz embedding of finite metric spaces in Hilbert space, Israel J. Math., 52 (1985), pp. 46--52.

[13]

T. N. Bui and C. Jones, Finding good approximate vertex and edge partitions is np-hard, Inf. Process. Lett., 42 (1992), pp. 153--159.

Digital Library

[14]

S. Chawla, A. Gupta, and H. Raecke, Embeddings of negative-type metrics and improved approximations to sparsest cut, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, Canada, January 2005.

Digital Library

[15]

E. D. Demaine and M. Hajiaghayi, Bidimensionality: New connections between FPT algorithms and PTASs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, Canada, January 2005.

Digital Library

[16]

-------------, Graphs excluding a fixed minor have grids as large as treewidth, with combinatorial and algorithmic applications through bidimensionality, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2005), Vancouver, Canada, January 2005.

Digital Library

[17]

E. D. Demaine, M. Hajiaghayi, N. Nishimura, P. Ragde, and D. M. Thilikos, Approximation algorithms for classes of graphs excluding single-crossing graphs as minors, Journal of Computer and System Sciences, 69 (2004), pp. 166--195.

Digital Library

[18]

G. Even, J. Naor, S. Rao, and B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, J. ACM, 47 (2000), pp. 585--616.

Digital Library

[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]

U. Feige, Relations between average case complexity and approximation complexity, in Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, ACM Press, 2002, pp. 534--543.

Digital Library

[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]

U. Feige and G. Schechtman, On the optimality of the random hyperplane rounding technique for MAX CUT, Random Structures Algorithms, 20 (2002), pp. 403--440.

Digital Library

[23]

J. R. Gilbert, J. P. Hutchinson, and R. E. Tarjan, A separator theorem for graphs of bounded genus, J. Algorithms, 5 (1984), pp. 391--407.

Digital Library

[24]

M. Grohe, Local tree-width, excluded minors, and approximation algorithms, Combinatorica, 23 (2003), pp. 613--632.

Digital Library

[25]

L. H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combinatorial Theory, 1 (1966), pp. 385--393.

[26]

J. A. Kelner, Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus, in Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, ACM Press, 2004, pp. 455--464.

Digital Library

[27]

S. Khot, Ruling out PTAS for graph min-bisection, densest subgraph and bipartite clique, in 45th Annual Symposium on Foundations of Computer Science, IEEE Computer Soc., 2004.

Digital Library

[28]

S. Khot and N. Vishnoi, On embeddability of negative type metrics into l1. Manuscript, 2004.

[29]

P. N. Klein, S. A. Plotkin, and S. Rao, Excluded minors, network decomposition, and multicommodity flow, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, 1993, pp. 682--690.

Digital Library

[30]

R. Krauthgamer, J. R. Lee, M. Mendel, and A. Naor, Measured descent: A new embedding method for finite metrics, in 45th Symposium on Foundations of Computer Science, 2004.

Digital Library

[31]

E. L. Lawler, Combinatorial optimization: networks and matroids, Holt, Rinehart and Winston, New York, 1976.

[32]

J. R. Lee, On distance scales, embeddings, and efficient relaxations of the cut cone, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, Vancouver, 2005, ACM.

Digital Library

[33]

F. T. Leighton, Complexity Issues in VLSI: Optimal Layout for the Shuffle-Exchange Graph and Other Networks, MIT Press, Cambridge, MA, 1983.

Digital Library

[34]

T. Leighton and S. Rao, Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms, J. ACM, 46 (1999), pp. 787--832.

Digital Library

[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.

Digital Library

[38]

G. L. Miller, S.-H. Teng, W. Thurston, and S. A. Vavasis, Separators for sphere-packings and nearest neighbor graphs, J. ACM, 44 (1997), pp. 1--29.

Digital Library

[39]

------------, Geometric separators for finite-element meshes, SIAM J. Sci. Comput., 19 (1998), pp. 364--386.

Digital Library

[40]

Y. Rabinovich, On average distortion of embedding metrics into the line and into L1, in 35th Annual ACM Symposium on Theory of Computing, ACM, 2003.

Digital Library

[41]

S. Rao, Small distortion and volume preserving embeddings for planar and Euclidean metrics, in Proceedings of the 15th Annual Symposium on Computational Geometry, New York, 1999, ACM, pp. 300--306.

Digital Library

[42]

N. Robertson and P. D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7 (1986), pp. 309--322.

[43]

N. Robertson and P. D. Seymour, Graph minors. X. Obstructions to tree-decomposition, Journal of Combinatorial Theory Series B, 52 (1991), pp. 153--190.

Digital Library

[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.

Cited By

Anand ALee ELi JSaranurak TMohar BShinkar IO'Donnell R(2024)Approximating Small Sparse CutsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649747(319-330)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649747
Liu KChen LYu JJia Z(2024)Revisiting RFID Missing Tag Identification: Theoretical Foundation and Algorithm DesignIEEE/ACM Transactions on Networking10.1109/TNET.2024.340447132:5(4056-4066)Online publication date: Oct-2024
https://doi.org/10.1109/TNET.2024.3404471
Guo ALi JSukprasert PKhuller SDeshpande AMukherjee K(2024)To Store or Not to Store: a graph theoretical approach for Dataset Versioning2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS57955.2024.00049(479-493)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPS57955.2024.00049
Show More Cited By

Index Terms

Improved approximation algorithms for minimum-weight vertex separators
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Improved Approximation Algorithms for Minimum Weight Vertex Separators

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 $L_1$ (and even Euclidean embeddings) are insufficient but that the additional ...
Improved Approximation Algorithms for the Vertex Cover Problem in Graphs and Hypergraphs

We obtain improved algorithms for finding small vertex covers in bounded degree graphs and hypergraphs. We use semidefinite programming to relax the problems and introduce new} rounding techniques for these relaxations. On graphs with maximum degree at ...
On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s---t separators that induce graphs having certain properties. It is known that finding a minimum clique s---t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221---232, 1985), while for example ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '05: Proceedings of the thirty-seventh annual ACM symposium on Theory of computing

May 2005

778 pages

ISBN:1581139608

DOI:10.1145/1060590

General Chair:
Hal Gabow
University of Colorado
,
Program Chair:
Ronald Fagin
IBM Almaden Research Center

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 22 May 2005

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC05

Sponsor:

STOC05: Symposium on Theory of Computing

May 22 - 24, 2005

MD, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
876
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)11

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anand ALee ELi JSaranurak TMohar BShinkar IO'Donnell R(2024)Approximating Small Sparse CutsProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649747(319-330)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649747
Liu KChen LYu JJia Z(2024)Revisiting RFID Missing Tag Identification: Theoretical Foundation and Algorithm DesignIEEE/ACM Transactions on Networking10.1109/TNET.2024.340447132:5(4056-4066)Online publication date: Oct-2024
https://doi.org/10.1109/TNET.2024.3404471
Guo ALi JSukprasert PKhuller SDeshpande AMukherjee K(2024)To Store or Not to Store: a graph theoretical approach for Dataset Versioning2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS57955.2024.00049(479-493)Online publication date: 27-May-2024
https://doi.org/10.1109/IPDPS57955.2024.00049
Kammer FMeintrup JSajenko A(2022)Space-Efficient Vertex Separators for TreewidthAlgorithmica10.1007/s00453-022-00967-384:9(2414-2461)Online publication date: 29-Apr-2022
https://doi.org/10.1007/s00453-022-00967-3
Mayer RJacobsen HLi GLi ZIdreos SSrivastava D(2021)Hybrid Edge Partitioner: Partitioning Large Power-Law Graphs under Memory ConstraintsProceedings of the 2021 International Conference on Management of Data10.1145/3448016.3457300(1289-1302)Online publication date: 9-Jun-2021
https://dl.acm.org/doi/10.1145/3448016.3457300
Kamath CKlein KPietrzak K(2021)On Treewidth, Separators and Yao’s GarblingTheory of Cryptography10.1007/978-3-030-90453-1_17(486-517)Online publication date: 4-Nov-2021
https://doi.org/10.1007/978-3-030-90453-1_17
Krauthgamer RLee JRika HChan T(2019)Flow-cut gaps and face covers in planar graphsProceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3310435.3310468(525-534)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.5555/3310435.3310468
Chiang DDrewes FGildea DLopez ASatta G(2018)Weighted dag automata for semantic graphsComputational Linguistics10.1162/COLI_a_0030944:1(119-186)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1162/COLI_a_00309
Heidari SSimmhan YCalheiros RBuyya R(2018)Scalable Graph Processing FrameworksACM Computing Surveys10.1145/319952351:3(1-53)Online publication date: 12-Jun-2018
https://dl.acm.org/doi/10.1145/3199523
Brandt SWattenhofer R(2018)Approximating Small Balanced Vertex Separators in Almost Linear TimeAlgorithmica10.1007/s00453-018-0490-xOnline publication date: 7-Aug-2018
https://doi.org/10.1007/s00453-018-0490-x
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents