Currently, what conditions are known to be sufficient for the SDP relaxation of MaxCut to be exact?

$\begingroup$ Can you be a bit more detailed and specific? $\endgroup$ – András Bátkai Jul 15 '19 at 7:36

$\begingroup$ Thanks Andras, I was thinking of a priori properties of the gaph that would ensure exactness of the SDP relaxation. For instance, it is known that controlling the crossing number can lead to a polynomial time algorithm as in arxiv.org/abs/1903.06061. I would like to know if e.g. a certain bound on the crossing number could be sufficient for the SDP relaxation to be exact. Or any other parameter about the graph as well if easier to study in relationship with the SDP relaxation. $\endgroup$ – SGC Jul 15 '19 at 11:11

$\begingroup$ I'd be surprised if crossing number helped much. Note that already for the 5gon (a planar graph) the SDP in question is not exact. $\endgroup$ – Dima Pasechnik Jul 15 '19 at 12:24

$\begingroup$ thanks for this comment ! Is there another parameter you think could be more appropriate for the exactness analysis of the SDP relaxation ? $\endgroup$ – SGC Jul 15 '19 at 13:25
This question was studied somewhat in the early '90s (before GoemansWilliamson, in fact; note that it was Delorme and Poljak who first gave a polytime SDP algorithm for MaxCut, conjecturing that the 5cycle gave the worst approximation ratio).
Graphs for which the MaxCut value and the SDP relaxation coincided were called 'exact'. As Dima says, there are not too many classes of exact graphs, with bipartite graphs being one of the main cases. A number of results and examples are given in the paper "The performance of an eigenvalue bound on the maxcut problem in some classes of graphs" by Delorme and Poljak; probably the best place to start looking.
Note that it is unlikely there is an exact characterization, since it was shown (again by Delorme and Poljak, in "Combinatorial properties and the complexity of a maxcut approximation") that deciding if a given weighted graph is exact is NPcomplete. To be fair, they state therein that they do not know the complexity of recognizing unweighted exact graphs.

$\begingroup$ Is it now known $5$cycle gives worst approximation? $\endgroup$ – T.... Jul 15 '19 at 23:37

2$\begingroup$ Not quite. The worst possible ratio between the SDP value and the true MaxCut is ~ 1.138, given by certain geometric graphs devised by Feige and Schechtman. The 5cycle's ratio is (25+5sqrt(5))/32 ~ 1.131. $\endgroup$ – Ryan O'Donnell Jul 16 '19 at 0:02

1$\begingroup$ (I should add that, among all graphs whose maxcut is at most 4/5 of the edges, the 5cycle achieves the highest SDP value.) $\endgroup$ – Ryan O'Donnell Jul 16 '19 at 0:04


1$\begingroup$ Perhaps cs.cmu.edu/~odonnell/papers/optimalmaxcut.pdf $\endgroup$ – Ryan O'Donnell Jul 16 '19 at 10:14
An obvious sufficient condition is that the SDP in question has a rank$1$ optimal solution. Indeed, the SDP provides you with an upper bound on the MAXCUT value, and then you pay the price of $\alpha=0.878\dots$ (i.e. your optimal value gets multiplied by $\alpha$) rounding it to a rank one (no longer optimal) solution; so if you can skip the rounding, you're done.
25 years ago (when the original GoemansWilliams paper appeared) it was already known that for random graphs $\alpha$ is much closer to $1$, I don't know whether much more is known nowadays.

$\begingroup$ Thanks Dima, I was thinking about a priori sufficient conditions based on properties of the graph. For instance, we know that Perron Frobenius type of properties could be relevant, since they would insure multiplicity one of the eigenvalue relaxation and thus, differentiability of the dual function, which would entail exactness of the eigenvalue relaxation (and of the SDP via a well known equivalence). $\endgroup$ – SGC Jul 15 '19 at 11:02