Fast approximate graph partitioning algorithms

Guy Even, Joseph Naor, Satish Rao, Baruch Schieber

Research output: Contribution to journalArticlepeer-review

76 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)2187-2214
Number of pages28
JournalSIAM Journal on Computing
Volume28
Issue number6
DOIs
StatePublished - 1999
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Fast approximate graph partitioning algorithms'. Together they form a unique fingerprint.

Cite this