Currently, what conditions are known to be sufficient for the SDP relaxation of Max-Cut to be exact?
$\begingroup$
$\endgroup$
4
-
$\begingroup$ Can you be a bit more detailed and specific? $\endgroup$– András BátkaiCommented Jul 15, 2019 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$– SGCCommented Jul 15, 2019 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 PasechnikCommented Jul 15, 2019 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$– SGCCommented Jul 15, 2019 at 13:25
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
6
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.
answered Jul 15, 2019 at 18:28
-
$\begingroup$ Is it now known $5$-cycle gives worst approximation? $\endgroup$– TurboCommented Jul 15, 2019 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$ Commented Jul 16, 2019 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$ Commented Jul 16, 2019 at 0:04
-
$\begingroup$ Good reference for these approximation facts? $\endgroup$– TurboCommented Jul 16, 2019 at 0:12
-
1$\begingroup$ Perhaps cs.cmu.edu/~odonnell/papers/optimal-max-cut.pdf $\endgroup$ Commented Jul 16, 2019 at 10:14
$\begingroup$
$\endgroup$
2
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.
answered Jul 15, 2019 at 10:46
-
$\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$– SGCCommented Jul 15, 2019 at 11:02
-
$\begingroup$ arxiv.org/pdf/2109.02238.pdf This paper (2021) establish conditions under which graphs of certain classes have rank 1 solutions to the max-cut SDP. $\endgroup$– tonyCommented Feb 29 at 13:14