On exactness of SDP relaxation for the maximum cut problem

Semidefinite programming provides a relaxation of the maximum cut problem on a graph. Given a graph G with rational weights, the decision problem of whether this relaxation is exact on G is known to be N P -complete since Delorme-Poljak (1993), but its complexity was unresolved for unweighted graphs. In this work, we extend the N P -completeness result for unweighted graphs. We then investigate and present a few classes of graphs for which the semidefinite relaxation of the maximum cut problem is exact. For each class, we determine the optimal objective value by explicitly constructing a maximum cut and prove the uniqueness of the exact solution for two of these classes. Finally, we address two open problems posed by Mirka and Williamson (2024) concerning the rank of the optimal solutions of an exact semidefinite relaxation, providing corresponding counterexamples.