Tight bounds for the min-max boundary decomposition cost of weighted graphs

SPAA 2006.

PDF

abstract

Many load balancing problems that arise in scientific computing applications boil down to the problem of partitioning a graph with weights on the vertices and costs on the edges into a given number of equally-weighted parts such that the maximum boundary cost over all parts is small.

Here, this partitioning problem is considered for graphs $G=(V,E)$ with edge costs $c\colon E\to \mathbb R_{\ge 0}$, that have bounded maximum degree and a $p$-separator theorem for some $p>1$, i.e., any (arbitrarily weighted) subgraph of $G$ can be separated into two parts of roughly the same weight by removing a separator $S\subseteq V$ such that the edges incident to $S$ in the subgraph have total cost at most proportional to $(\sum_e c^p_e)^{1/p}$, where the sum is over all edges in the subgraph.

For arbitrary weights $w\colon V\to \mathbb R_{\ge 0}$, we show that the vertices of such graphs can be partitioned into $k$ parts such that the weight of each part differs from the average weight $\sum_{v\in V}w_v/k$ by at most $(1-\frac{1}{k})\max_{v\in V}w_v$, and the boundary edges of each part have total cost at most proportional to $(\sum_{e\in E}c_e^p/k)^{1/p}+\max_{e\in E}c_e$. The partition can be computed in time nearly proportional to the time for computing separators $S$ for $G$ as above.

Our upper bound is shown to be tight up to a constant factor for infinitely many instances with a broad range of parameters. Previous results achieved this bound only if one has $c\equiv 1$, $w\equiv 1$, and one allows parts of weight as large as a constant multiple of the average weight.

We also give a separator theorem for $d$-dimensional grid graphs with arbitrary edge costs, which is the first result of its kind for non-planar graphs.