Theory Seminar: Min-Max Graph Partitioning and Small Set Expansion

Roy Schwartz (CS, Technion)

Wednesday, 6.4.2011, 12:30

Taub 401 (Note unusual room)

We study graph partitioning problems from a min-max perspective,
in which an input graph on $n$ vertices should be partitioned into $k$ parts,
and the objective is to minimize the maximum number of edges leaving a single
part. The two main versions we consider are where the $k$ parts need to be
of equal-size, and where they must separate a set of $k$ given terminals.
We consider a common generalization of these two problems, and design for it
an $O(\sqrt{\log n}\log^{3/2} k)$-approximation algorithm. This improves over
an $O(\log^2 n)$ approximation for the version of separating $k$ given
terminals due to Svitkina and Tardos \cite{ST04}, and roughly $O(k\log n)$ approximation
for the version where the parts need to be of equal size that follows from
other previous work.

The main tool we use is a new approximation algorithm for \emph{$\rho$-unbalanced-cut}, the problem of finding in an input graph $G=(V,E)$ a set $S\subseteq V$ of size $|S|=\rho n$ that minimizes the number of edges leaving $S$. We provide a bicriteria approximation of $O(\sqrt{\log{n}\log{(1/\rho)}})$ for this problem. Note that the special case $\rho = 1/2$ is just the \emph{minimum bisection} problem, and indeed our bound generalizes that of Arora, Rao and Vazirani \cite{ARV08} which only applies to the case where $\rho = \Omega(1)$. Our algorithm also works for the closely related \emph{small-set-expansion} problem, which asks for a set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum conductance (edge-expansion), and was suggested recently by Raghavendra and Steurer~\cite{RS10}. In fact, our algorithm handles more general, weighted, versions of both problems. Previously, an $O(\log n)$ true approximation for both $\rho$-unbalanced-cut and small-set-expansion was known following from R\"acke~\cite{Racke08}.

Joint work with: Nikhil Bansal, Robi Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan and Seffi Naor.

The main tool we use is a new approximation algorithm for \emph{$\rho$-unbalanced-cut}, the problem of finding in an input graph $G=(V,E)$ a set $S\subseteq V$ of size $|S|=\rho n$ that minimizes the number of edges leaving $S$. We provide a bicriteria approximation of $O(\sqrt{\log{n}\log{(1/\rho)}})$ for this problem. Note that the special case $\rho = 1/2$ is just the \emph{minimum bisection} problem, and indeed our bound generalizes that of Arora, Rao and Vazirani \cite{ARV08} which only applies to the case where $\rho = \Omega(1)$. Our algorithm also works for the closely related \emph{small-set-expansion} problem, which asks for a set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum conductance (edge-expansion), and was suggested recently by Raghavendra and Steurer~\cite{RS10}. In fact, our algorithm handles more general, weighted, versions of both problems. Previously, an $O(\log n)$ true approximation for both $\rho$-unbalanced-cut and small-set-expansion was known following from R\"acke~\cite{Racke08}.

Joint work with: Nikhil Bansal, Robi Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan and Seffi Naor.