TY - JOUR

T1 - Min-max graph partitioning and small set expansion

AU - Bansal, Nikhil

AU - Feige, Uriel

AU - Krauthgamer, Robert

AU - Makarychev, Konstantin

AU - Nagarajan, Viswanath

AU - Naor, Joseph Seffi

AU - Schwartz, Roy

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( v log n log k) approximation algorithm. This improves over an O(log2 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 ? V of size |S| ≤pn with minimum edge expansion. We give an O(log n log (1/p)) 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( v log n log k) approximation algorithm. This improves over an O(log2 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 ? V of size |S| ≤pn with minimum edge expansion. We give an O(log n log (1/p)) bicriteria approximation algorithm for small-set expansion in general graphs, and an improved factor of O(1) for graphs that exclude any fixed minor.

KW - Balanced cut

KW - Expansion

KW - Sparse cut

KW - Spreading metrics

UR - http://www.scopus.com/inward/record.url?scp=84899646612&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84899646612&partnerID=8YFLogxK

U2 - 10.1137/120873996

DO - 10.1137/120873996

M3 - Article

AN - SCOPUS:84899646612

SN - 0097-5397

VL - 43

SP - 872

EP - 904

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 2

ER -