CONSTRUCTIVE HEURISTICS AND LOWER BOUNDS FOR GRAPH PARTITIONING BASEDON A PRINCIPAL-COMPONENTS APPROXIMATION

This paper addresses the problem of partitioning the vertex set of an edge-weighted undirected graph into two parts of specified sizes so as to minimize the sum of the weights on edges joining vertices in diffe rent parts. This problem is NP-hard and has several important applicat ions in which the graph size is typically large and the brute-force ap proach (of listing all feasible partitions and comparing costs) is com putationally prohibitive. In this paper a new class of algorithms is d eveloped on the basis of a transformation of the graph problem to a ge ometric problem of clustering a set of points in Euclidean space. Inst ead of searching through all feasible partitions that meet the size sp ecifications, it is shown that the search can be confined to a set of n(p(p+1)/2) partitions, where n is the number of vertices in the graph and p is the rank of the n x n graph connection matrix. Procedures ar e developed for constructing all such partitions in O(n(p(p+3)/2)) tim e. For matrices with large ranks, approximation of the connection matr ix by a matrix of low rank by using principal-components analysis is s uggested. The algorithms presented in this paper are constructive algo rithms in that they generate a feasible partition of the graph directl y from the connection matrix, as opposed to iterative algorithms that start from a feasible partition as an initial guess. The algorithms al so bound the difference between the achieved cost and the lowest achie vable cost. These lower bounds on the cost of the optimal partition ar e proved to be superior to the Donath-Hoffman lower bound for two sign ificant special cases wherein either the two part sizes are equal or t he graph connection matrix has equal row sums. Simulation results on r andomly constructed graphs of different sizes clearly demonstrate the effectiveness of these heuristics in terms of both the cost of the con structed partition and the lower bound provided.