Spreading metric based approximate graph partitioning algorithms

that have many applications in circuit testing and simulation, VLSI
layout, and sparse linear system solving.

We unify two well known graph partitioning problems (separators and
$k$-multiway separators) into a new partitioning 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 connected
component is at most $\rho$ times the weight of the vertex set in the
graph. The problem of finding a minimum capacity $\rho$-separator is
NP-complete, and therefore, we develop approximation algorithms for this
problem. We present an $O(\log n )$-approximation algorithm for
$\rho$-separators. This result improves slightly the approximation
factor of the Leighton-Rao algorithm for separators, and improves by
a factor of $\log k$ previous approximation algorithms for
$k$-multiway separators.

Our algorithm is simple and the talk assumes no previous acquaintance
with the subject.