Nonuniform Graph Partitioning with Just a Little Flex

In the nonuniform graph partitioning problem, we are given a capacitated graph G on n vertices, and numbers n1, n2, ..., nk summing to n. The goal is to partition the vertices of G into parts S1, S2, ..., Sk with |Si| = ni for each i, and minimizing the capacity of edges crossing between distinct parts. This generalizes, for instance, the well-known graph bisection problem. In order to obtain meaningful results, it is necessary to consider a bicriteria approximation, where we allow part sizes to be violated by a multiplicative factor ϵ (i.e., |Si| ≤ (1 + ϵ) ni for each i). If all part sizes are equal - uniform graph partitioning - an O(logn) approximation is possible for any constant ϵ > 0, via a dynamic programming approach. But for nonuniform graph partitioning, no results were known without a substantial violation factor, the best result being an O(√lognlogk) approximation with ϵ ≈ 5. Existing approaches to nonuniform graph partitioning seem to inherently rely on at least a factor 2 violation; whereas the dynamic programming approach for uniform graph partitioning do not extend. In this paper we take a completely different approach to give the first results for arbitrary small violation, showing an O(logn/ϵ) approximation for any constant ϵ > 0. Our approach involves a number of novel ingredients: a refinement of Räcke decomposition trees; a "compression scheme"to decrease certain search spaces to polynomial size; a strong linear program based around local consistency within large neighborhoods; and a rounding scheme for this LP.