Approximating edge expansion, equivalently finding sparse cuts in graphs is a fundamental problem in combinatorial optimization that has received considerable attention in both theory and practice. Yet, the complexity of approximating edge expansion in graphs is poorly understood.
Particularly, worse is the understanding of the approximability of the expansion of small sets in graphs. More formally, current algorithmic or hardness results do not settle the approximability of the following problem: Given a regular graph G and a very small constant c, find a set S of cn vertices in the graph such that minimum number of edges cross the set S.
Recently it was shown that the complexity of this problem is closely tied to the Unique Games Conjecture. Furthermore, we show that the hardness of this problem is a natural assumption that generalizes the unique games conjecture, and yields hardness for problems like Balanced Separator and Minimum Linear arrangement.
In this talk, we motivate the problem, and survey recent work consisting of algorithms and interesting connections within graph expansion, and its relation to Unique Games Conjecture.
Copyright. All Rights Reserved.