E5.9 RANK REDUCTION IN GRAPH PARTITIONING

This paper addresses the problem of partitioning the vertex set of an edge-weighted undirected graph into !WO parts of specified sizes so that the cost of the partition defined as the sum of the weights on edges joining vertices in different parts is minimized. This problem is NP-Hard and has several important applications in VLSI layout, where the graph size is typically large and the bruteforce approach of listing all feasible partitions and comparing costs is computationally prohibitive. We show in this paper that if the n Xn connection matrix of the graph has rank p , then the search can be confined to a smaller set of nP@+')I2 partitions. Procedures are developed for constructing all such partitions in O(np@+3)/2) time. For matrices with large rank, we suggest a principal components approximation of the connection matrix. Our algorithms also provide a bound on the proximity of the cost of the constructed partition to the optimal cost based on the eigenvalues left out in the rank reduction process.