Paper Info
Title
Graph expansion and the unique games conjecture
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].
Year
DOI
Venue
2010
10.1145/1806689.1806792
STOC
Keywords
Field
DocType
optimization problem,hardness of approximation,regular graph,unique games conjecture
Discrete mathematics,Graph,Combinatorics,Unique games conjecture,Vertex (geometry),Hardness of approximation,Graph expansion,Conductance,Small set,Optimization problem,Mathematics
Conference
ISSN
Citations 
PageRank 
0737-8017
92
2.99
References 
Authors
25
2
Name
Order
Citations
PageRank
Prasad Raghavendra1101350.58
David Steurer293444.91