A Copositive Programming Approach to Graph Partitioning

Janez Povh, Franz Rendl

SIAM Journal on Optimization · 2007 · 73 citations · 13 references

Concepts

TL;DR

The 3‑partition problem is closely related to NP‑hard problems such as bandwidth determination and vertex separator finding. The authors aim to minimize the total weight of edges between two of the three partition sets of specified sizes and to tighten the resulting semidefinite bound. They formulate the problem as a linear program over the cone of completely positive matrices, which naturally yields semidefinite relaxations, including the spectral relaxation of Helmberg et al. The spectral relaxation is shown to be equivalent to a semidefinite program, and the proposed tightened SDP delivers a noticeably better bound on small instances.

Abstract

We consider 3‐partitioning the vertices of a graph into sets $S_1$, $S_2$, and $S_3$ of specified cardinalities, such that the total weight of all edges joining $S_1$ and $S_2$ is minimized. This problem is closely related to several NP‐hard problems like determining the bandwidth or finding a vertex separator in a graph. We show that this problem can be formulated as a linear program over the cone of completely positive matrices, leading in a natural way to semidefinite relaxations of the problem. We show in particular that the spectral relaxation introduced by Helmberg et al. (1995) can equivalently be formulated as a semidefinite program. Finally we propose a tightened version of this semidefinite program and show on some small instances that this new bound is a significant improvement over the spectral bound.

References

13