On exactness of SDP relaxation for the maximum cut problem

Avinash Bhardwaj, Hritiz Gogoi, Vishnu Narayanan +1

Semidefinite programming (SDP) provides a powerful relaxation for the maximum cut problem. In this work, we characterize a few classes of graphs for which the SDP relaxation is exa…