Graph expansion and the Unique Games Conjecture

with Prasad Raghavendra. STOC 2010.

PDF

Invited to STOC 2010 special issue

abstract

In this work, we investigate the connection between Graph Expansion and the Unique Games Conjecture. The edge expansion of a subset of vertices $S \subseteq V$ in a graph $G$ measures the fraction of edges that leave $S$. In a $d$-regular graph, the edge expansion/conductance $\Phi (S)$ of a subset $S \subseteq V$ is defined as $$\Phi (S) = \frac{|E(S, V\setminus S)|}{d|S|}.$$ Approximating the conductance of small linear sized sets (size $\delta n$) is a natural optimization question that is a variant of the well-studied problem. However, there are no known algorithms to even distinguish between almost complete edge expansion ($\Phi (S) = 1-\varepsilon$), and close to $0$ expansion.

• 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 stronger variant of the 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 [Arora et al., STOC’08]

keywords

• Unique Games Conjecture
• small-set expansion
• hardness reduction