8
$\begingroup$

I'm looking at page 28 of Lovasz "Semidefinite programs and combinatorial optimization" and it gives the following approximation of independence number of the graph

$$\max u' Z u$$ subject to $$Z\succ 0$$ $$Z_{ij}=0 \ \forall ij\in E(G)$$ $$tr(Z)=1$$

Can I get independent set (or something close to an independent set) directly from the solution of SDP relaxation? Lovasz says that SDP is the only known way to solve this problem exactly for perfect graphs, is that still true?

Clarification: there's a similar SDP relaxation for the size of maximum cut, and I can get the full solution (the actual cut, rather than its size) by taking square root of Z and doing randomized rounding (Ch.6 of Williamson/Shmoys book). I'm wondering if there's a similar technique for this problem

Improve this question
$\endgroup$
4
  • $\begingroup$ For the first question, I don't really get what you mean by "the actual independent set". The SDP is a relaxation, and so the optimal value of the SDP bounds the independence number from above. If they differ, no independent set attains the optimal value of the SDP. This can be the case if the graph is not perfect. Could you make it more explicit what you require for your "actual independent set"? $\endgroup$
    – Yoshio Okamoto
    Commented Mar 4, 2011 at 0:25
  • $\begingroup$ I want to get largest independent set rather than "size of largest independent set" $\endgroup$
    – Yaroslav Bulatov
    Commented Mar 4, 2011 at 1:15
  • $\begingroup$ Thanks for clarification, but I'm still wondering. The SDP for max cut is used for approximation. Namely, the randomized rounding gives a cut that has value "close" to the optimal cut value, not necessarily a real max cut. If you need a similar technique, I guess what you really want is an independent set that has size close to the independence number. Or, do you concentrate on perfect graphs, or want to deal with general graphs? $\endgroup$
    – Yoshio Okamoto
    Commented Mar 4, 2011 at 1:38
  • $\begingroup$ I want to find Maximum Independent Set in Perfect Graph. ipsofacto gives a solution, but it requires solving several SDPs $\endgroup$
    – Yaroslav Bulatov
    Commented Mar 4, 2011 at 2:11

2 Answers 2

Reset to default
4
$\begingroup$

I believe SDP is the only known technique to solve the maximum independent set problem on perfect graphs. To get the independent set, one could do the following. Guess if a vertex is in the independent set, delete it and solve the SDP. If it returns the same value, then there is an independent set without this vertex. So, make this vertex adjacent to all other vertices, and continue. This should give you an actual independent set.

Otherwise, we have identified one vertex of the independent set, and we can remove it and continue on the remaining graph.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Moreover, this has been implemented and works quite well (with some optimizations): E. Alper Yıldırım and Xiaofei Fan-Orzechowski, On Extracting Maximum Stable Sets in Perfect Graphs Using Lovász's Theta Function, Computational Optimization and Applications 33, 229–247, 2006. dx.doi.org/10.1007/s10589-005-3060-5 $\endgroup$
    – András Salamon
    Commented Mar 4, 2011 at 11:03
  • $\begingroup$ Interesting...it seems that perfection is not required for SDP estimate of independence number to be exact (here's example mathoverflow.net/questions/57336/…), so this should work for a larger class of graphs $\endgroup$
    – Yaroslav Bulatov
    Commented Mar 4, 2011 at 20:33
  • $\begingroup$ @Yaroslav: You're right, perfection is not required. But if you adapt the strategy ipsofacto suggested, you will need the deletion of vertices also has the same property. This condition is automatically satisfied if the graph is perfect, but otherwise you need to be careful. $\endgroup$
    – Yoshio Okamoto
    Commented Mar 5, 2011 at 10:40
2
$\begingroup$

I'm not sure if Lovasz's comment still holds. There has been some recent work on this (and related) problems on perfect graphs. You should take a look at the following link for techniques that involve message passing rather than solving SDPs: http://www.cs.columbia.edu/~jebara/papers/uai09perfect.pdf

Improve this answer
$\endgroup$
5
  • $\begingroup$ Interesting paper, do I understand it correctly that if max-product converges on a perfect graph, then greedy decoding will recover maximum independent set? $\endgroup$
    – Yaroslav Bulatov
    Commented Mar 4, 2011 at 4:12
  • $\begingroup$ I've skimmed the paper, but I couldn't find how the methods solve the maximum independent set problem for perfect graphs in polynomial time. The number of maximal cliques can be exponential in a perfect graph, and so running times in Corollaries 1 and 2 are not polynomial. Although I don't understand the contents of Section 7 very much, I don't see which linear optimization problem the method in Section 7 solves. The experiments are performed for the maximum matching problem, but not for the maximum independent set problem. $\endgroup$
    – Yoshio Okamoto
    Commented Mar 4, 2011 at 4:43
  • $\begingroup$ @yoshio You are correct. The LP for MWIS is known to be integral if you include the appropriate constraints over all of the (exponentially many) cliques. And it is the perfectness of the clique graph that the paper discusses. It looks like the authors only conjecture that max-product on a NMRF always produces the correct MAP assignment. $\endgroup$
    – Nicholas Ruozzi
    Commented Mar 4, 2011 at 14:51
  • $\begingroup$ Thanks. Then, can I assume that the paper does not give a polynomial-time algorithm for the maximum independent set problem for perfect graphs? $\endgroup$
    – Yoshio Okamoto
    Commented Mar 5, 2011 at 10:42
  • $\begingroup$ @YoshioOkamoto: it seems so. A recent paper gives an example of a perfect graph where this approach converges to wrong solution. Figure 3 of "Revisiting MAP Estimation, Message Passing and Perfect Graphs" (datalab.uci.edu/papers/AISTATS_perfect_graphs.pdf) $\endgroup$
    – Yaroslav Bulatov
    Commented Sep 20, 2011 at 0:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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