research-article

Sparsest cut on bounded treewidth graphs: algorithms and hardness results

Authors:

David WitmerAuthors Info & Claims

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

Pages 281 - 290

https://doi.org/10.1145/2488608.2488644

Published: 01 June 2013 Publication History

Abstract

We give a 2-approximation algorithm for the non-uniform Sparsest Cut problem that runs in time n^O(k), where k is the treewidth of the graph. This improves on the previous 2^{2^k}-approximation in time poly(n) 2^O(k) due to Chlamtac et al. [18].

To complement this algorithm, we show the following hardness results: If the non-uniform Sparsest Cut has a ρ-approximation for series-parallel graphs (where ρ ≥ 1), then the MaxCut problem has an algorithm with approximation factor arbitrarily close to 1/ρ. Hence, even for such restricted graphs (which have treewidth 2), the Sparsest Cut problem is NP-hard to approximate better than 17/16 - ε for ε > 0; assuming the Unique Games Conjecture the hardness becomes 1/α_GW - ε. For graphs with large (but constant) treewidth, we show a hardness result of 2 - ε assuming the Unique Games Conjecture.

Our algorithm rounds a linear program based on (a subset of) the Sherali-Adams lift of the standard Sparsest Cut LP. We show that even for treewidth-2 graphs, the LP has an integrality gap close to 2 even after polynomially many rounds of Sherali-Adams. Hence our approach cannot be improved even on such restricted graphs without using a stronger relaxation.

References

[1]

C. Ambühl, M. Mastrolilli, and O. Svensson. Inapproximability results for maximum edge biclique, minimum linear arrangement, and sparsest cut. SIAM J. Comput., 40(2):567--596, 2011.

Digital Library

[2]

E. Amir. Approximation algorithms for treewidth. Algorithmica, 56(4):448--479, 2010.

Digital Library

[3]

S. Arnborg, D. Corneil, and A. Proskurowski. Complexity of finding embeddings in a k-tree. SIAM Journal on Algebraic Discrete Methods, 8(2):277--284, 1987.

Digital Library

[4]

S. Arora, J. R. Lee, and A. Naor. Euclidean distortion and the sparsest cut. J. Amer. Math. Soc., 21(1):1--21, 2008.

[5]

S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. J. ACM, 56(2):Art. 5, 37, 2009.

Digital Library

[6]

D. Bienstock and N. Ozbay. Tree-width and the Sherali-Adams operator. Discrete Optim., 1(1):13--21, 2004.

Digital Library

[7]

H. Bodlaender. NC-algorithms for graphs with small treewidth. In Graph-Theoretic Concepts in Computer Science, volume 344 of LNCS, pages 1--10. 1989.

Digital Library

[8]

H. Bodlaender. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing, 25(6):1305--1317, 1996.

Digital Library

[9]

H. L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth. Theoretical Computer Science, 209:1--45, 1998.

Digital Library

[10]

B. Brinkman and M. Charikar. On the impossibility of dimension reduction in $l_1$. J. ACM, 52(5):766--788, 2005.

Digital Library

[11]

A. Chakrabarti, A. Jaffe, J. R. Lee, and J. Vincent. Embeddings of topological graphs: Lossy invariants, linearization, and 2-sums. In FOCS, pages 761--770, 2008.

Digital Library

[12]

M. Charikar, K. Makarychev, and Y. Makarychev. Integrality gaps for Sherali-Adams relaxations. In STOC, pages 283--292. 2009.

Digital Library

[13]

S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar. On the hardness of approximating multicut and sparsest-cut. Comput. Complexity, 15(2):94--114, 2006.

Digital Library

[14]

J. Cheeger, B. Kleiner, and A. Naor. A (log n)^Ω(1) integrality gap for the sparsest cut SDP. In FOCS, pages 555--564. 2009.

Digital Library

[15]

J. Cheeger, B. Kleiner, and A. Naor. Compression bounds for Lipschitz maps from the Heisenberg group to L_1. Acta Math., 207(2):291--373, 2011.

[16]

C. Chekuri, A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Embedding k-outerplanar graphs into $\ell_1$. SIAM J. Discrete Math., 20(1):119--136, 2006.

Digital Library

[17]

C. Chekuri, F. B. Shepherd, and C. Weibel. Flow-cut gaps for integer and fractional multiflows. In SODA, pages 1198--1208, 2010.

Digital Library

[18]

E. Chlamtác, R. Krauthgamer, and P. Raghavendra. Approximating sparsest cut in graphs of bounded treewidth. In APPROX, volume 6302 of LNCS, pages 124--137. 2010.

Digital Library

[19]

J. Chuzhoy and S. Khanna. Polynomial flow-cut gaps and hardness of directed cut problems. J. ACM, 56(2):Art. 6, 28, 2009.

Digital Library

[20]

P. Crescenzi, R. Silvestri, and L. Trevisan. On weighted vs unweighted versions of combinatorial optimization problems. Inform. and Comput., 167(1):10--26, 2001.

Digital Library

[21]

R. Diestel. Graph theory, volume 173 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2000.

[22]

E. Friedgut. Boolean functions with low average sensitivity depend on few coordinates. Combinatorica, 18(1):27--35, 1998.

[23]

A. Gupta, I. Newman, Y. Rabinovich, and A. Sinclair. Cuts, trees and $\ell_1$-embeddings of graphs. Combinatorica, 24(2):233--269, 2004.

Digital Library

[24]

V. Guruswami and A. K. Sinop. Certifying graph expansion and non-uniform sparsity via generalized spectra. In SODA, 2013.

[25]

V. Guruswami, A. K. Sinop, and Y. Zhou. Constant factor lasserre integrality gaps for graph partitioning problems. CoRR, abs/1202.6071, 2012.

[26]

J. Håstad. Some optimal inapproximability results. J. ACM, 48(4):798--859, 2001.

Digital Library

[27]

S. Khot, G. Kindler, E. Mossel, and R. O'Donnell. Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? SIAM J. Comput., 37(1):319--357, 2007.

Digital Library

[28]

S. Khot and R. Saket. SDP integrality gaps with local l_1-embeddability. In FOCS 09, pages 565--574. IEEE Computer Soc., Los Alamitos, CA, 2009.

Digital Library

[29]

S. Khot and N. K. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l$_\mbox1$. In FOCS, pages 53--62, 2005.

Digital Library

[30]

P. Klein, S. A. Plotkin, and S. B. Rao. Excluded minors, network decomposition, and multicommodity flow. In STOC, pages 682--690, 1993.

Digital Library

[31]

R. Krauthgamer and Y. Rabani. Improved lower bounds for embeddings into L_1. SIAM J. Comput., 38(6):2487--2498, 2009.

Digital Library

[32]

J. R. Lee and A. Naor. Embedding the diamond graph in $L_p$ and dimension reduction in L_1. Geom. Funct. Anal., 14(4):745--747, 2004.

[33]

J. R. Lee and A. Naor. l_p metrics on the Heisenberg group and the Goemans-Linial conjecture. In FOCS, pages 99--108, 2006.

Digital Library

[34]

J. R. Lee and P. Raghavendra. Coarse differentiation and multi-flows in planar graphs. Discrete Comput. Geom., 43(2):346--362, 2010.

Digital Library

[35]

J. R. Lee and A. Sidiropoulos. On the geometry of graphs with a forbidden minor. In STOC, pages 245--254. 2009.

Digital Library

[36]

J. R. Lee and A. Sidiropoulos. Near-optimal distortion bounds for embedding doubling spaces into $L_1$ {extended abstract}. In STOC, pages 765--772. 2011.

Digital Library

[37]

N. Linial, E. London, and Y. Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 15(2):215--245, 1995.

[38]

A. Magen and M. Moharrami. Robust algorithms for max independent set on minor-free graphs based on the Sherali-Adams hierarchy. In APPROX, volume 5687 of LNCS, pages 258--271. Springer, Berlin, 2009.

Digital Library

[39]

D. W. Matula and F. Shahrokhi. Sparsest cuts and bottlenecks in graphs. Discrete Appl. Math., 27(1--2):113--123, 1990.

Digital Library

[40]

E. Mossel, R. O'Donnell, and K. Oleszkiewicz. Noise stability of functions with low influences: invariance and optimality. Ann. of Math. (2), 171(1):295--341, 2010.

[41]

I. Newman and Y. Rabinovich. A lower bound on the distortion of embedding planar metrics into Euclidean space. Discrete Comput. Geom., 29(1):77--81, 2003.

[42]

H. Okamura and P. D. Seymour. Multicommodity flows in planar graphs. J. Combin. Theory Ser. B, 31(1):75--81, 1981.

[43]

Y. Rabinovich. On average distortion of embedding metrics into the line and into l_1. In STOC, pages 456--462, 2003.

Digital Library

[44]

P. Raghavendra and D. Steurer. Integrality gaps for strong SDP relaxations of Unique Games. In FOCS, pages 575--585. 2009.

Digital Library

[45]

S. Rao. Small distortion and volume preserving embeddings for planar and Euclidean metrics. In SOCG, pages 300--306, 1999.

Digital Library

[46]

O. Regev. Entropy-based bounds on dimension reduction in l_1. Israel Journal of Mathematics, 2012. arXiv:1108.1283.

[47]

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

[48]

L. Trevisan, G. B. Sorkin, M. Sudan, and D. P. Williamson. Gadgets, approximation, and linear programming. SIAM J. Comput., 29(6):2074--2097, 2000.

Digital Library

[49]

M. J. Wainwright and M. I. Jordan. Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations. Technical Report 671, UC Berkeley, September 2004.

Cited By

Chalermsook PKaul MMnich MSpoerhase JUniyal SVaz D(2024)Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial DiameterACM Transactions on Algorithms10.1145/363262320:1(1-20)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3632623
Cohen-Addad VMömke TVerdugo V(2024)A 2-approximation for the bounded treewidth sparsest cut problem in $$\textsf{FPT}$$ TimeMathematical Programming10.1007/s10107-023-02044-1206:1-2(479-495)Online publication date: 4-Jan-2024
https://doi.org/10.1007/s10107-023-02044-1
Alimi MDaneshgar AForoughmand-Araabi M(2022)Mean Isoperimetry with Control on Outliers: Exact and Approximation AlgorithmsTheoretical Computer Science10.1016/j.tcs.2022.05.022Online publication date: May-2022
https://doi.org/10.1016/j.tcs.2022.05.022
Show More Cited By

Index Terms

Sparsest cut on bounded treewidth graphs: algorithms and hardness results
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in $FPT$ Time
Integer Programming and Combinatorial Optimization
Abstract
In the non-uniform sparsest cut problem, we are given a supply graph G and a demand graph D, both with the same set of nodes V. The goal is to find a cut of V that minimizes the ratio of the total capacity on the edges of G crossing the cut over ...
Restricted space algorithms for isomorphism on bounded treewidth graphs

The Graph Isomorphism problem restricted to graphs of bounded treewidth or bounded tree distance width are known to be solvable in polynomial time. We give restricted space algorithms for these problems proving the following results:*Isomorphism for ...
The complexity of finding uniform sparsest cuts in various graph classes

Given an undirected graph G=(V,E), the (uniform, unweighted) sparsest cut problem is to find a vertex subset S@?V minimizing |E(S,S@?)|/(|S||S@?|). We show that this problem is NP-complete, and give polynomial time algorithms for various graph classes. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '13: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing

June 2013

998 pages

ISBN:9781450320290

DOI:10.1145/2488608

General Chairs:
Dan Boneh
Stanford University, USA
,
Tim Roughgarden
Stanford University, USA
,
Program Chair:
Joan Feigenbaum
Yale University, USA

Copyright © 2013 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

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'13

Sponsor:

SIGACT

STOC'13: Symposium on Theory of Computing

June 1 - 4, 2013

California, Palo Alto, USA

Acceptance Rates

STOC '13 Paper Acceptance Rate 100 of 360 submissions, 28%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

19
Total Citations
View Citations
270
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)2

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chalermsook PKaul MMnich MSpoerhase JUniyal SVaz D(2024)Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial DiameterACM Transactions on Algorithms10.1145/363262320:1(1-20)Online publication date: 22-Jan-2024
https://dl.acm.org/doi/10.1145/3632623
Cohen-Addad VMömke TVerdugo V(2024)A 2-approximation for the bounded treewidth sparsest cut problem in $$\textsf{FPT}$$ TimeMathematical Programming10.1007/s10107-023-02044-1206:1-2(479-495)Online publication date: 4-Jan-2024
https://doi.org/10.1007/s10107-023-02044-1
Alimi MDaneshgar AForoughmand-Araabi M(2022)Mean Isoperimetry with Control on Outliers: Exact and Approximation AlgorithmsTheoretical Computer Science10.1016/j.tcs.2022.05.022Online publication date: May-2022
https://doi.org/10.1016/j.tcs.2022.05.022
Cohen-Addad VMömke TVerdugo V(2022)A 2-Approximation for the Bounded Treewidth Sparsest Cut Problem in $$\mathsf {FPT}$$ TimeInteger Programming and Combinatorial Optimization10.1007/978-3-031-06901-7_9(112-125)Online publication date: 27-May-2022
https://doi.org/10.1007/978-3-031-06901-7_9
Braun GPokutta SRoy A(2018)Strong reductions for extended formulationsMathematical Programming: Series A and B10.5555/3288898.3288958172:1-2(591-620)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288958
Baïou MBarahona F(2018)Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problemMathematical Programming: Series A and B10.5555/3288898.3288957172:1-2(59-75)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288957
Shen XLee JNagarajan V(2018)Approximating graph-constrained max-cutMathematical Programming: Series A and B10.5555/3288898.3288945172:1-2(35-58)Online publication date: 1-Nov-2018
https://dl.acm.org/doi/10.5555/3288898.3288945
Abraham IFiltser AGupta ANeiman ODiakonikolas IKempe DHenzinger M(2018)Metric embedding via shortest path decompositionsProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing10.1145/3188745.3188808(952-963)Online publication date: 20-Jun-2018
https://dl.acm.org/doi/10.1145/3188745.3188808
Braun GPokutta SRoy A(2018)Strong reductions for extended formulationsMathematical Programming10.1007/s10107-018-1316-y172:1-2(591-620)Online publication date: 25-Aug-2018
https://doi.org/10.1007/s10107-018-1316-y
Baïou MBarahona F(2018)Sparsest cut in planar graphs, maximum concurrent flows and their connections with the max-cut problemMathematical Programming10.1007/s10107-017-1227-3172:1-2(59-75)Online publication date: 27-Jan-2018
https://doi.org/10.1007/s10107-017-1227-3
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