TY - JOUR

T1 - Min-max graph partitioning and small set expansion

AU - Bansal, N.

AU - Feige, U.

AU - Krauthgamer, R.

AU - Makarychev, K.

AU - Nagarajan, V.

AU - Naor, J.

AU - Schwartz, R.

PY - 2014

Y1 - 2014

N2 - 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 k})$ approximation algorithm. This improves over an $O(\log^2 n)$ approximation for the second version due to Svitkina and Tardos [Min-max multiway cut, in APPROX-RANDOM, 2004, Springer, Berlin, 2004], and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an $O(1)$ approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the small-set expansion problem. In this problem, we are given a graph $G$ and the goal is to find a nonempty set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum edge expansion. We give an $O(\sqrt{\log{n}\log{(1/\rho)}})$ bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of $O(1)$ for graphs that exclude any fixed minor.

AB - 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 k})$ approximation algorithm. This improves over an $O(\log^2 n)$ approximation for the second version due to Svitkina and Tardos [Min-max multiway cut, in APPROX-RANDOM, 2004, Springer, Berlin, 2004], and roughly $O(k\log n)$ approximation for the first version that follows from other previous work. We also give an $O(1)$ approximation algorithm for graphs that exclude any fixed minor. Our algorithm uses a new procedure for solving the small-set expansion problem. In this problem, we are given a graph $G$ and the goal is to find a nonempty set $S\subseteq V$ of size $|S| \leq \rho n$ with minimum edge expansion. We give an $O(\sqrt{\log{n}\log{(1/\rho)}})$ bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of $O(1)$ for graphs that exclude any fixed minor.

U2 - 10.1137/120873996

DO - 10.1137/120873996

M3 - Article

VL - 43

SP - 872

EP - 904

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

SN - 0097-5397

IS - 2

ER -