Algorithms for graph partitioning problems by means of eigenspace relaxations

Graph partitioning problems are NP-hard problems and very important in VLSI design. We study relations among several eigenvalue bounds and algorithms for graph partitioning problems. Also, we design an algorithm for the problems which performs the following: first it computes the k largest eigenvalues of the affine symmetric matrix function to attain Donath-Hoffman bound; then it calculates a relaxed partition which is an array constant factor of an eigenspace associated with k eigenvalues; finally it generates an actual partition from the relaxed solution of a method similar to Boppana's algorithm. To compute optimal eigenvalue bounds, one needs to solve eigenvalue optimization problems which minimize the sum of the k largest eigenvalues of the nonsmooth functions. We use a subgradient method to compute the Donath-Hoffman eigenvalue bound. Numerical results indicate that although the Donath-Hoffman bound is not tight for graph partitioning problems, our algorithm can generate optimal partitions.