Min-Max-Boundary Domain Decomposition

Authors: Marcos Kiwi, Daniel A. Spielman and Shang-Hua Teng.

Bibliographic Information: Appeared in Special issue of Theoretical Computer Science for COCOON'98, volume 261, issue 2, 2001, pp. 253-266

An extended abstract appeared in Proceedings of the 4-th Annual International Computing and Combinatorics Conference - COCOON, 1998.


Motivated by domain decomposition, one of the most effective and popular parallel numerical techniques, we study the following {\sf min-max boundary} multi-way partitioning problem: Given a graph $G$ and a positive integer $k$, we would like to divide $G$ into $k$ subgraphs $G_1,...,G_k$ (by removing edges) such that (i) $|G_i| = \Theta(n/k)$ for all $i$ in the range $1\leq i\leq k$; and (ii) the maximum boundary size of any subgraph (the set of edges connecting it with other subgraphs) is minimized.

We obtain the following result: Let $G$ be a well-shaped mesh in $d$ dimensions. Then $G$ can be partitioned in $k$ subgraphs $G_1$,...,$G_k$ such that for all $i$ in the range $1\leq i\leq k$, $G_i$ has $\Theta(n/k)$ vertices and the number of edges connecting $G_i$ with other subgraphs is bounded by $O(n/k)^{1-1/d}$. Similar results (with $d = 2$) are also given for planar graphs and graphs with bounded genus and forbidden minors. Furthermore, our algorithm can find such a partition in $O(n\log k)$ time. We also extend this result to weighted graphs and vertex-based graph decomposition. You can download this paper as Postscript, compressed Postscript, PDF, or compressed PDF.

Daniel A. Spielman
Last modified: Sun Aug 26 11:57:40 2001