A COMPUTATIONAL STUDY OF GRAPH PARTITIONING

Let G = (N, E) be an edge-weighted undirected graph. The graph partiti oning problem is the problem of partitioning the node set N into k dis joint subsets of specified sizes so as to minimize the total weight of the edges connecting nodes in distinct subsets of the partition. We p resent a numerical study on the use of eigenvalue-based techniques to find upper and lower bounds for this problem. Results for bisecting gr aphs with up to several thousand nodes are given, and for small graphs some trisection results are presented. We show that the techniques ar e very robust and consistently produce upper and lower bounds having a relative gap of typically a few percentage points.