<p>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. </p>

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

CC BY-SA 2.5
2011-03-04T11:03:26.127Z
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.  http://dx.doi.org/10.1007/s10589-005-3060-5
András Salamon
CC BY-SA 2.5
2011-03-04T20:33:48.163Z
Interesting...it seems that perfection is not required for SDP estimate of independence number to be exact (here's example http://mathoverflow.net/questions/57336/lovasz-theta-function-integrality), so this should work for a larger class of graphs
Yaroslav Bulatov
CC BY-SA 2.5
2011-03-05T10:40:48.410Z
@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.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-03T20:18:23.270Z
2011-03-03T20:18:23.270Z
ipsofacto
<p>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:  <a href="http://www.cs.columbia.edu/~jebara/papers/uai09perfect.pdf" rel="nofollow">http://www.cs.columbia.edu/~jebara/papers/uai09perfect.pdf</a></p>

CC BY-SA 2.5
2011-03-04T04:12:14.130Z
Interesting paper, do I understand it correctly that if max-product converges on a perfect graph, then greedy decoding will recover maximum independent set?
Yaroslav Bulatov
CC BY-SA 2.5
2011-03-04T04:43:08.540Z
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.
Yoshio Okamoto
CC BY-SA 2.5
2011-03-04T14:51:38.943Z
@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.
Nicholas Ruozzi
CC BY-SA 2.5
2011-03-05T10:42:24.490Z
Thanks. Then, can I assume that the paper does not give a polynomial-time algorithm for the maximum independent set problem for perfect graphs?
Yoshio Okamoto
CC BY-SA 3.0
2011-09-20T00:59:04.747Z
@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" (http://www.datalab.uci.edu/papers/AISTATS_perfect_graphs.pdf)
Yaroslav Bulatov
CC BY-SA 2.5
2011-03-04T03:17:47.700Z
2011-03-04T03:17:47.700Z
Nicholas Ruozzi
<p>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</p>

<p>$$\max u&#39; Z u$$
subject to
$$Z\succ 0$$
$$Z_{ij}=0 \ \forall ij\in E(G)$$
$$tr(Z)=1$$</p>

<p>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?</p>

<p>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</p>

CC BY-SA 2.5
2011-03-04T00:25:40.113Z
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"?
Yoshio Okamoto
CC BY-SA 2.5
2011-03-04T01:15:42.720Z
I want to get largest independent set rather than "size of largest independent set"
Yaroslav Bulatov
CC BY-SA 2.5
2011-03-04T01:38:07.770Z
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?
Yoshio Okamoto
CC BY-SA 2.5
2011-03-04T02:11:38.067Z
I want to find Maximum Independent Set in Perfect Graph. ipsofacto gives a solution, but it requires solving several SDPs
Yaroslav Bulatov
<ds.algorithms><graph-theory><semidefinite-programming><independent-set>
SDP relaxation of independent set
Yaroslav Bulatov
# SDP relaxation of independent set

(Asked by: username_0 on 2011-03-03)

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

**Tags:** ds.algorithms, graph-theory, semidefinite-programming, independent-set
> **Comments:**
> **username_1**: 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"?  
> **username_0**: I want to get largest independent set rather than "size of largest independent set"  
> **username_1**: 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?  
> **username_0**: I want to find Maximum Independent Set in Perfect Graph. ipsofacto gives a solution, but it requires solving several SDPs  

---

## 2 answers

### Answer by username_2 on 2011-03-03. Score: 4 | Accepted answer

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.

> **Comments:**
> **username_3**: 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.  http://dx.doi.org/10.1007/s10589-005-3060-5  
> **username_0**: Interesting...it seems that perfection is not required for SDP estimate of independence number to be exact (here's example http://mathoverflow.net/questions/57336/lovasz-theta-function-integrality), so this should work for a larger class of graphs  
> **username_1**: @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.  

---

### Answer by username_4 on 2011-03-04. Score: 2

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>

> **Comments:**
> **username_0**: Interesting paper, do I understand it correctly that if max-product converges on a perfect graph, then greedy decoding will recover maximum independent set?  
> **username_1**: 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.  
> **username_4**: @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.  
> **username_1**: Thanks. Then, can I assume that the paper does not give a polynomial-time algorithm for the maximum independent set problem for perfect graphs?  
> **username_0**: @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" (http://www.datalab.uci.edu/papers/AISTATS_perfect_graphs.pdf)  

---

