research-article

Graph expansion and the unique games conjecture

Authors:

Prasad Raghavendra,

David SteurerAuthors Info & Claims

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

Pages 755 - 764

https://doi.org/10.1145/1806689.1806792

Published: 05 June 2010 Publication History

Abstract

The edge expansion of a subset of vertices S ⊆ V in a graph G measures the fraction of edges that leave S. In a d-regular graph, the edge expansion/conductance Φ(S) of a subset S ⊆ V is defined as Φ(S) = (|E(S, V\S)|)/(d|S|). Approximating the conductance of small linear sized sets (size δ n) is a natural optimization question that is a variant of the well-studied Sparsest Cut problem. However, there are no known algorithms to even distinguish between almost complete edge expansion (Φ(S) = 1-ε), and close to 0 expansion. In this work, we investigate the connection between Graph Expansion and the Unique Games Conjecture. Specifically, we show the following: We show that a simple decision version of the problem of approximating small set expansion reduces to Unique Games. Thus if approximating edge expansion of small sets is hard, then Unique Games is hard. Alternatively, a refutation of the UGC will yield better algorithms to approximate edge expansion in graphs. This is the first non-trivial "reverse" reduction from a natural optimization problem to Unique Games. Under a slightly stronger UGC that assumes mild expansion of small sets, we show that it is UG-hard to approximate small set expansion. On instances with sufficiently good expansion of small sets, we show that Unique Games is easy by extending the techniques of [4].

References

[1]

N. Alon. Eigenvalues and expanders. Combinatorica, 6(2):83--96, 1986.

Digital Library

[2]

N. Alon and V. D. Milman. lambda₁, isoperimetric inequalities for graphs, and superconcentrators. Journal of Combinatorial Theory. Series B, 38:73--88, 1985.

[3]

S. Arora, R. Impagliazzo, W. Matthews, and D. Stuerer. Improved algorithms for unique games via divide and conquer. In Electronic Colloquium on Computational Complexity ECCCTR: TR10-041, 2010.

[4]

S. Arora, S. Khot, A. Kolla, D. Steurer, M. Tulsiani, and N. K. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In STOC, pages 21--28. ACM, 2008.

Digital Library

[5]

S. Arora, S. Rao, and U. Vazirani. Expander flows, geometric embeddings and graph partitioning. In Proceedings of the thirty-sixth annual ACM Symposium on Theory of Computing (STOC-04), pages 222--231, June 13--15 2004.

Digital Library

[6]

Y. Aumann and Y. Rabani. An O(log k) approximate min-cut max-flow theorem and approximation algorithm. SIAM Journal on Computing, 27(1):291--301, Feb. 1998.

Digital Library

[7]

B. Barak, M. Hardt, I. Haviv, A. Rao, O. Regev, and D. Steurer. Rounding parallel repetitions of unique games. In FOCS, pages 374--383. IEEE Computer Society, 2008.

Digital Library

[8]

M. Charikar, K. Makarychev, and Y. Makarychev. Integrality gaps for sherali-adams relaxations. In STOC, pages 283--292. ACM, 2009.

Digital Library

[9]

J. Cheeger. A lower bound on smallest eigenvalue of a laplacian. Problems in Analysis (Papers dedicated to Salomon Bochner), pages 195--199, 1970.

[10]

Feige and Schechtman. On the optimality of the random hyperplane rounding technique for MAX CUT. RSA: Random Structures Algorithms, 20, 2002.

Digital Library

[11]

U. Feige, G. Kindler, and R. O'Donnell. Understanding parallel repetition requires understanding foams. In IEEE Conference on Computational Complexity, pages 179--192, 2007.

Digital Library

[12]

K. Georgiou, A. Magen, T. Pitassi, and I. Tourlakis. Integrality gaps of 2 -- o(1) for vertex cover SDPs in the lovész-schrijver hierarchy. In FOCS, pages 702--712. IEEE Computer Society, 2007.

Digital Library

[13]

S. Khot. On the power of unique 2-prover 1-round games. In STOC, pages 767--775. ACM, 2002.

Digital Library

[14]

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

[15]

S. Khot and O. Regev. Vertex cover might be hard to approximate to within 2-ε. J. Comput. Syst. Sci., 74(3):335--349, 2008.

Digital Library

[16]

S. Khot and N. K. Vishnoi. The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l₁. In FOCS, pages 53--62. IEEE Computer Society, 2005.

Digital Library

[17]

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

Digital Library

[18]

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

[19]

P. Raghavendra. Optimal algorithms and inapproximability results for every CSP? In STOC, pages 245--254. ACM, 2008.

Digital Library

[20]

P. Raghavendra and D. Steurer. How to round any CSP. In FOCS, pages 586--594. IEEE Computer Society, 2009.

Digital Library

[21]

P. Raghavendra and D. Steurer. Integrality gaps for strong SDP relaxations of UNIQUE GAMES. In FOCS, pages 575--585. IEEE Computer Society, 2009.

Digital Library

[22]

P. Raghavendra, D. Steurer, and P. Tetali. Approximations for the isoperimetric and spectral profile of graphs and for restricted eigenvalues of diagonally-dominant matrices. In STOC. ACM, 2010. To Appear.

Digital Library

[23]

A. Rao. Parallel repetition in projection games and a concentration bound. In STOC, pages 1--10. ACM, 2008.

Digital Library

[24]

R. Raz. A counterexample to strong parallel repetition. In FOCS, pages 369--373. IEEE Computer Society, 2008.

Digital Library

[25]

G. Schoenebeck, L. Trevisan, and M. Tulsiani. A linear round lower bound for Lovász-Schrijver SDP relaxations of vertex cover. In IEEE Conference on Computational Complexity, pages 205--216, 2007.

Digital Library

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
Olesker-Taylor SZanetti L(2024)Geometric bounds on the fastest mixing Markov chainProbability Theory and Related Fields10.1007/s00440-023-01257-x188:3-4(1017-1062)Online publication date: 30-Jan-2024
https://doi.org/10.1007/s00440-023-01257-x
Jain VPham HVuong T(2023)Dimension reduction for maximum matchings and the Fastest Mixing Markov ChainComptes Rendus. Mathématique10.5802/crmath.447361:G5(869-876)Online publication date: 18-Jul-2023
https://doi.org/10.5802/crmath.447
Show More Cited By

Index Terms

Graph expansion and the unique games conjecture
1. Theory of computation
  1. Randomness, geometry and discrete structures

Recommendations

The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ₁

In this article, we disprove a conjecture of Goemans and Linial; namely, that every negative type metric embeds into ℓ₁ with constant distortion. We show that for an arbitrarily small constant δ > 0, for all large enough n, there is an n-point negative ...
Subexponential Algorithms for Unique Games and Related Problems

Subexponential time approximation algorithms are presented for the Unique Games and Small-Set Expansion problems. Specifically, for some absolute constant c, the following two algorithms are presented.

(1) An exp(kn^ϵ)-time algorithm that, given as input ...
Reductions between Expansion Problems
CCC '12: Proceedings of the 2012 IEEE Conference on Computational Complexity (CCC)

The Small-Set Expansion Hypothesis (Raghavendra, Steurer, STOC 2010) is a natural hardness assumption concerning the problem of approximating the edge expansion of small sets in graphs. This hardness assumption is closely connected to the Unique Games ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '10: Proceedings of the forty-second ACM symposium on Theory of computing

June 2010

812 pages

ISBN:9781450300506

DOI:10.1145/1806689

General Chair:
Michael Mitzenmacher
Harvard
,
Program Chair:
Leonard J. Schulman
Caltech

Copyright © 2010 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: 05 June 2010

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

STOC'10

Sponsor:

SIGACT

STOC'10: Symposium on Theory of Computing

June 5 - 8, 2010

Massachusetts, Cambridge, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

136
Total Citations
View Citations
539
Total Downloads

Downloads (Last 12 months)60
Downloads (Last 6 weeks)10

Reflects downloads up to 22 Oct 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
Olesker-Taylor SZanetti L(2024)Geometric bounds on the fastest mixing Markov chainProbability Theory and Related Fields10.1007/s00440-023-01257-x188:3-4(1017-1062)Online publication date: 30-Jan-2024
https://doi.org/10.1007/s00440-023-01257-x
Jain VPham HVuong T(2023)Dimension reduction for maximum matchings and the Fastest Mixing Markov ChainComptes Rendus. Mathématique10.5802/crmath.447361:G5(869-876)Online publication date: 18-Jul-2023
https://doi.org/10.5802/crmath.447
Jeronimo FWu PSaha BServedio R(2023)The Power of Unentangled Quantum Proofs with Non-negative AmplitudesProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585248(1629-1642)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585248
Jones CPotechin ARajendran GXu JSaha BServedio R(2023)Sum-of-Squares Lower Bounds for Densest k-SubgraphProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585221(84-95)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585221
Haeupler BHershkowitz DSaranurak TSaha BServedio R(2023)Maximum Length-Constrained Flows and Disjoint Paths: Distributed, Deterministic, and FastProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585202(1371-1383)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585202
Hubert Chan TTang ZXue Q(2023)Max-min greedy matching problem: Hardness for the adversary and fractional variantTheoretical Computer Science10.1016/j.tcs.2023.114329(114329)Online publication date: Dec-2023
https://doi.org/10.1016/j.tcs.2023.114329
Bentert Mvan Bevern RFluschnik TNichterlein ANiedermeier R(2023)Polynomial-time data reduction for weighted problems beyond additive goal functionsDiscrete Applied Mathematics10.1016/j.dam.2022.11.018328:C(117-133)Online publication date: 31-Mar-2023
https://dl.acm.org/doi/10.1016/j.dam.2022.11.018
Arulselvan AChinchuluun A(2023)Identifying Critical Nodes in a NetworkHandbook for Management of Threats10.1007/978-3-031-39542-0_16(325-339)Online publication date: 21-Jul-2023
https://doi.org/10.1007/978-3-031-39542-0_16
Chan TTang ZXue Q(2023)Max-Min Greedy Matching Problem: Hardness for the Adversary and Fractional VariantFrontiers of Algorithmics10.1007/978-3-031-39344-0_7(85-104)Online publication date: 26-Aug-2023
https://doi.org/10.1007/978-3-031-39344-0_7
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