Fast approximate graph partitioning algorithms

Abstract

We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-balanced partitions are unified into a new problem called minimum capacity ρ-separators. A ρ-separator is a subset of edges whose removal partitions the vertex set into connected components such that the sum of the vertex weights in each component is at most ρ times the weight of the graph. We present a new and simple O(log n)-approximation algorithm for minimum capacity ρ-separators which is based on spreading metrics yielding an O(log n)-approximation algorithm both for b-balanced cuts and k-balanced partitions. In particular, this result improves the previous best known approximation factor for k-balanced partitions in undirected graphs by a factor of O(log k). We enhance these results by presenting a version of the algorithm that obtains an O(log OPT)-approximation factor. The algorithm is based on a technique called spreading metrics that enables us to formulate directly the minimum capacity ρ-separator problem as an integer program. We also introduce a generalization called the simultaneous separator problem, where the goal is to find a minimum capacity subset of edges that separates a given collection of subsets simultaneously. We extend our results to directed graphs for values of ρ≥1/2. We conclude with an efficient algorithm for computing an optimal spreading metric for ρ-separators. This yields more efficient algorithms for computing b-balanced cuts than were previously known.