Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations

Avinash Bhardwaj, Chen Chen, Vishnu Narayanan

An exact Max-Cut semidefinite relaxation can have optima outside the convex hull of optimal cut matrices. We study when this hull equals the optimal face and how to recognize equal…