Expander flows, geometric embeddings and graph partitioning

2009/04/01 by Sanjeev Arora, Satish Rao, Umesh Vazirani · 2 citations
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Markov Chains and Monte Carlo Methods #Advanced Graph Theory Research #Expander graph #Mathematics #Combinatorics #Embedding #Discrete mathematics #Triangle inequality #Concentration of measure #Graph #Computer science

paper · doi:10.1145/1502793.1502794

openalex publication_date 2009/04/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/15

Abstract

We give a O (√log n )-approximation algorithm for the sparsest cut, edge expansion, balanced separator, and graph conductance problems. This improves the O (log n )-approximation of Leighton and Rao (1988). We use a well-known semidefinite relaxation with triangle inequality constraints. Central to our analysis is a geometric theorem about projections of point sets in R d , whose proof makes essential use of a phenomenon called measure concentration. We also describe an interesting and natural “approximate certificate” for a graph's expansion, which involves embedding an n -node expander in it with appropriate dilation and congestion. We call this an expander flow.

Citations

• Spectral graph theory [CBMS Conference on Recent Advances in Spectral Graph Theory held at California State University at Fresno, June 6 - 10. 1994]
• Eigenvalues and expanders
• On the nonexistence of uniform homeomorphisms between Lp-spaces
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Lectures on Discrete Geometry
• The geometry of graphs and some of its algorithmic applications

Cited by

• Inapproximability of Treewidth and Related Problems
• Cut (graph theory) [wikipedia]

Related

• Expander Decomposition with Almost Optimal Overhead
• Expander Graphs in Pure and Applied Mathematics
• Expander Decomposition for Non-Uniform Vertex Measures
• Towards a better approximation for sparsest cut?
• New Structures and Algorithms for Length-Constrained Expander Decompositions