2021/09/06 by Hong, Daniel, Lee, Hyunwoo, Wei, Alex
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.2109.02238
The max-cut problem is a classical graph theory problem which is NP-complete. The best polynomial time approximation scheme relies on semidefinite programming (SDP). We study the conditions under which graphs of certain classes have rank~1 solutions to the max-cut SDP. We apply these findings to look at how solutions to the max-cut SDP behave under simple combinatorial constructions. Our results determine when solutions to the max-cut SDP for cycle graphs are rank~1. We find the solutions to the max-cut SDP of the vertex~sum of two graphs. We then characterize the SDP solutions upon joining two triangle graphs by an edge~sum.