Fast approximate graph partitioning algorithms

We study graph partitioning problems on graphs with edge capacities and vertex weights. The problems of b-balanced cuts and k-multiway separators are unified with a new problem called minimum capacity {rho}-separators. A {rho}-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 {rho} times the weight of the graph. We present a new and simple O(log n)-approximation algorithm for minimum capacity {rho}-separators yielding an O(log n)-approximation algorithm both for b-balanced cuts and k-multiway separators. In particular, this result improves the previous best known approximation factor for k-multiway separators 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 {rho}-separator problem as an integer program. We also consider 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 {rho}more » {ge} {1/2}. We conclude with an efficient algorithm for computing an optimal spreading metric for {rho}-separators. This yields more efficient algorithms for computing b-balanced cuts than were previously known.« less