Exact Subgraph Relaxations for Max-Cut

Weare interested in computing good upper bounds for the Max-Cut problem, which isa well-known NP-hard graph optimization problem. In particular, we deal withtight and computationally tractable relaxations based on semidefiniteoptimization.

Weapply a hierarchy of relaxations based on `exact subgraphs' for which weproject the problem to small subgraphs and require an exact solution on them.Here the original model size does not change and only the number of constraintsgrows in each level. Using semidefinite optimization leads to the currentlybest approximation results for Max-Cut.