The Complexity of Approximating Vertex Expansion

We study the complexity of approximating the vertex expansion of graphs G = (V, E), defined as Φ V def = minSCV n . |N(S)|/(|S||V\S). We give a simple polynomialtime algorithm for finding a subset with vertex expansion O(√(Φ V log d)) where d is the maximum degree of the graph. Our main result is an...

Full description

Saved in:
Bibliographic Details
Main Authors: Louis, Anand, Raghavendra, Prasad, Vempala, Santosh
Format: Conference Proceeding
Language:English
Subjects:
Approximation algorithms
Approximation methods
Eigenvalues and eigenfunctions
Games
Graph Partitioning
Hardness of Approximation
Markov processes
Particle separators
Small Set Expansion
Testing
Vertex Expansion
Citations: Items that cite this one
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We study the complexity of approximating the vertex expansion of graphs G = (V, E), defined as Φ V def = minSCV n . |N(S)|/(|S||V\S). We give a simple polynomialtime algorithm for finding a subset with vertex expansion O(√(Φ V log d)) where d is the maximum degree of the graph. Our main result is an asymptotically matching lower bound: under the Small Set Expansion (SSE) hypothesis, it is hard to find a subset with expansion less than C(√(Φ V log d)) for an absolute constant C. In particular, this implies for all constant ε > 0, it is SSE-hard to distinguish whether the vertex expansion
ISSN:0272-5428
DOI:10.1109/FOCS.2013.46