Constructive Heuristics and Lower Bounds for Graph Partitioning Based on a Principal-Components Approximation
K.S. Arun, Vasant B. Rao · SIAM Journal on Matrix Analysis and Applications · 1993
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 different parts. This problem is NP-hard and has several important applications in which the graph size is typically large and the brute-force approach (of listing all feasible partitions and comparing costs) is computationally prohibitive. In this paper a new class of algorithms is developed on the basis of a transformation of the graph problem to a geometric problem of clustering a set of points in Euclidean space. Instead of searching through all feasible partitions that meet the size specifications, 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 \times n$ graph connection matrix. Procedures are developed for constructing all such partitions in $O( n^{p( p + 3 ) /2} )$ time. For matrices with large ranks, approximation of the connection matrix by a matrix of low rank by using principal-components analysis is suggested. The algorithms presented in this paper are constructive algorithms in that they generate a feasible partition of the graph directly from the connection matrix, as opposed to iterative algorithms that start from a feasible partition as an initial guess. The algorithms also bound the difference between the achieved cost and the lowest achievable cost. These lower bounds on the cost of the optimal partition are proved to be superior to the Donath–Hoffman lower bound for two significant special cases wherein either the two part sizes are equal or the graph connection matrix has equal row sums. Simulation results on randomly constructed graphs of different sizes clearly demonstrate the effectiveness of these heuristics in terms of both the cost of the constructed partition and the lower bound provided.