Algorithms for graph partitioning problems by means of eigenspace relaxations

Graph partitioning problems are NP-hard problems and very important in very large-scale integration 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.