Semidefinite Programming and Graph Equipartition

Stefan E. Karisch and Franz Rendl

Semidefinite relaxations are used to approximate the problem of partitioning a graph into equally sized components. The relaxations extend previous eigenvalue based models, and combine semidefinite and polyhedral approaches. Computational results on graphs with several hundred vertices are given, and indicate that semidefinite relaxations approximate the equipartition problem quite well.

Report 302 - CDLDO 55, Department of Mathematics, Graz University of Technology, Graz, Austria, December 1995.