Rank reduction in graph partitioning

The problem of partitioning the vertex set of an edge-weighted undirected graph into two 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 is addressed. This problem is NP-hard and has several important applications in VLSI layout, where the graph size is typically large and the brute-force approach of listing all feasible partitions and comparing costs is computationally prohibitive. It is shown that if the n*n connection matrix of the graph has rank p, then the search can be confined to a smaller set of n/sup p(p+1)/2/ partitions. Procedures are developed for constructing all such partitions in O(n/sup p(p+3)/2/) time. For matrices with large rank, a principal components approximation of the connection matrix is suggested. The algorithms 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. >