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

| cite | improve this question | | | | |
  • $\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 5-gon (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 Goemans--Williamson, in fact; note that it was Delorme and Poljak who first gave a poly-time SDP algorithm for Max-Cut, conjecturing that the 5-cycle gave the worst approximation ratio).

Graphs for which the Max-Cut 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 max-cut 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 max-cut approximation") that deciding if a given weighted graph is exact is NP-complete. To be fair, they state therein that they do not know the complexity of recognizing unweighted exact graphs.

| cite | improve this answer | | | | |
  • $\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 Max-Cut is ~ 1.138, given by certain geometric graphs devised by Feige and Schechtman. The 5-cycle'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 max-cut is at most 4/5 of the edges, the 5-cycle achieves the highest SDP value.) $\endgroup$ – Ryan O'Donnell Jul 16 '19 at 0:04
  • $\begingroup$ Good reference for these approximation facts? $\endgroup$ – T.... Jul 16 '19 at 0:12
  • 1
    $\begingroup$ Perhaps cs.cmu.edu/~odonnell/papers/optimal-max-cut.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 Goemans-Williams 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.

| cite | improve this answer | | | | |
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.