<p>This LP is half-integral for all graphs, i.e., an optimal solution exists such that each variable is in {0,1/2,1}. It simply follows from a theorem of Nemhauser and Trotter. Of course the same conclusion of half-integrality follows for the LP of the complement problem (vertex cover). When the graph is bipartite the solution is integral. It follows simply from max-flow min-cut theorem or working with extreme point solutions of this LP. Also, the 1/2 edges form an odd-cycle. </p>

<p>Of course, this LP is no good for solving IS problem. Adding Clique constraints or SDPs are a much better approach. </p>

<p>Vertex packings: structural properties and algorithms
GL Nemhauser and Trotter- Math. Program., 1975</p>

CC BY-SA 2.5
2011-03-01T16:34:27.510Z
Right, see also Theorem 5.6 of [this paper](http://portal.acm.org/citation.cfm?id=365411.365412) for a very simple algorithm that efficiently *finds* a half-integral solution.
Jukka Suomela
CC BY-SA 2.5
2011-03-01T19:22:15.923Z
LP with Clique constraints solved about 50% more graphs from the set above....where can I find SDP formulation?
Yaroslav Bulatov
CC BY-SA 2.5
2011-03-01T16:07:27.993Z
2011-03-01T16:07:27.993Z
Mohit Singh
<p>There is another way to get a "relaxed version of maximal independent set". Instead of having as constraints "for each edge, the sum is at most 1", the constraints are "for each complete subgraph, the edge is at most 1". Which means : for each edge, for each triangle, for each $K_4$ and so on.</p>

<p>This is called the fractional independent set number. You will find some information there :
<a href="http://en.wikipedia.org/wiki/Fractional_coloring" rel="nofollow">http://en.wikipedia.org/wiki/Fractional_coloring</a>
or in the book "Fractional graph theory" from Daniel Ullman and Edward Scheinerman ( <a href="http://www.ams.jhu.edu/~ers/fgt/" rel="nofollow">http://www.ams.jhu.edu/~ers/fgt/</a> ).</p>

<p>Practically, this formulation is NP-Hard to compute, even though all the variables are continuous --> the number of cliques is exponential, and hard to compute.... But you are free to only enumerate some special cliques, for example just the edges (which you just did), or edges+triangles, or all the cliques up to $K_k$. After all, the value can only become "more representative" of the real integer value (*) :-)</p>

<p>Nathann</p>

<p>(*) this being said, you theoretically hav an arbitrarily large difference between the optimal result in the LP where all the cliques are represented and the optimal independent set</p>

CC BY-SA 3.0
2013-12-17T03:13:16.290Z
@YaroslavBulatov There is a reason for your observation. The clique inequalities and nonnegativity bounds provide the convex hull of independent sets if and only if the graph is perfect. Chordal graphs are perfect.
Austin Buchanan
CC BY-SA 2.5
2011-02-27T10:32:04.097Z
One of the problems with this approach is that if you have a non-bipartite cubic *triangle-free* graph (and there are plenty of those...), the formulation is exactly equal to that in the question, and we have exactly the same bad news. More generally, I think we can always construct graphs in which all nodes are in a $k$-clique and there is no $(k+1)$-clique, and show that $x_i = 1/k$ for all $i$ is the unique optimal solution of the LP.
Jukka Suomela
CC BY-SA 2.5
2011-02-28T06:13:31.200Z
interesting, this seems to be related to easiness of IndependentSet in chordal graphs
Yaroslav Bulatov
CC BY-SA 2.5
2011-03-01T08:40:25.717Z
I did some experiments, and the solution of this LP relaxation was always integral in chordal graphs
Yaroslav Bulatov
CC BY-SA 2.5
2011-02-27T07:31:49.260Z
2011-02-27T07:31:49.260Z
Nathann Cohen
<p><a href="http://etd.fcla.edu/UF/UFE0001011/butenko_s.pdf">Sergiy Butenko's Ph.D thesis</a> from 2003 reviews some other LP relaxations of MIS, as well as some quadratic relaxations. </p>

CC BY-SA 2.5
2011-02-27T21:10:03.513Z
2011-02-27T21:10:03.513Z
Suresh Venkat
<p>Non-bipartite connected cubic graphs have the unique optimal solution $x_i = 1/2$; in a bipartite cubic graph you have an integral optimal solution.</p>

<hr>

<p><em>Proof:</em> In a cubic graph, if you sum over all $3n/2$ constraints $x_i + x_j \le 1$, you have $\sum_i 3 x_i \le 3n/2$, and hence the optimum is at most $n/2$.</p>

<p>The solution $x_i = 1/2$ for all $i$ is trivially feasible, and hence also optimal.</p>

<p>In a bipartite cubic graph, each part has half of the nodes, and the solution $x_i = 1$ in one part is hence also optimal.</p>

<p>Any optimal solution must be tight, that is, we must have $\sum_i 3 x_i = 3n/2$ and hence $x_i + x_j = 1$ for each edge $\{i,j\}$. Thus if you have an odd cycle, you must choose $x_i = 1/2$ for each node in the cycle. And then if the graph is connected, this choice gets propagated everywhere.</p>

CC BY-SA 2.5
2011-02-27T01:46:40.523Z
As I wrote in a comment on the question, you only need the bipartiteness to prove existence of an integral optimal solution (but this requires a different proof from yours).
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-27T10:25:19.760Z
@Tsuyoshi: Yes, König's theorem is good to keep in mind. For example, together with the above observation, it will show that any bipartite cubic graph has a 1-factorisation (i.e., it can be partitioned in three perfect matchings). Of course this is the "wrong" way to prove this result, but I think it nicely demonstrates the power of König's theorem – if you just remember König's theorem, there are lots of classical results in graph theory that you can then re-invent easily.
Jukka Suomela
CC BY-SA 2.5
2011-02-26T22:24:19.730Z
2011-02-26T22:24:19.730Z
Jukka Suomela
<p>I've tried the following LP relaxation of maximum independent set</p>

<p><span class="math-container">$$\max \sum_i x_i$$</span></p>

<p><span class="math-container">$$\text{s.t.}\  x_i+x_j\le 1\  \forall (i,j)\in E$$</span>
<span class="math-container">$$x_i\ge 0$$</span></p>

<p>I get <span class="math-container">$1/2$</span> for every variable for every cubic non-bipartite graph I tried.</p>

<ol>
<li>Is true for all connected cubic non-bipartite graphs?</li>
<li>Is there LP relaxation which works better for such graphs?</li>
</ol>

<p><b>Update 03/05</b>:</p>

<p>Here's the result of clique-based LP relaxation suggested by Nathan</p>

<p><a href="https://i.sstatic.net/8CJTK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8CJTK.png" alt=""></a></p>

<p>I've summarized experiments <a href="http://yaroslavvb.blogspot.com/2011/03/linear-programming-for-maximum.html" rel="nofollow noreferrer">here</a>  Interestingly, there seem to be quite a few non-bipartite graphs for which the simplest LP relaxation is integral.</p>

CC BY-SA 2.5
2011-02-26T22:00:05.180Z
The solution $x_i = 1/2$ is certainly not unique. In a cubic bipartite graph, you can have an optimal solution with $x_i = 1$ in one part and $x_i = 0$ in the other part.
Jukka Suomela
CC BY-SA 2.5
2011-02-26T22:06:04.003Z
Sorry, I missed important part, I consider non-bipartite cubic graphs only. Every bipartite cubic graph I tried had an integral solution
Yaroslav Bulatov
CC BY-SA 2.5
2011-02-26T22:08:38.200Z
You also need to add "connected" if you want to avoid non-unique solutions.
Jukka Suomela
CC BY-SA 2.5
2011-02-26T22:22:47.653Z
(1) You forgot to write the nonnegativity constraints.  (2) For bipartite graphs, the optimal value of this LP relaxation is always equal to the maximum size of an independent set.  This is an immediate corollary of [König’s theorem](http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29).
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-27T02:01:46.290Z
@Yaroslav: A side question: how do you draw these graphs?
Tim
CC BY-SA 2.5
2011-02-27T10:33:31.257Z
@Tim: Mathematica, I would guess. :)
Jukka Suomela
CC BY-SA 2.5
2011-02-27T21:04:59.250Z
Here Mathematica notebook I used -- http://yaroslavvb.com/upload/save/cstheory-indsetLP.nb
Yaroslav Bulatov
CC BY-SA 2.5
2011-03-02T08:52:13.803Z
@Yaroslav Bulatov, Sorry for this question, but what's the software you used to drowing graphs?
Saeed
<graph-theory><co.combinatorics><linear-programming>
LP relaxation of independent set
Yaroslav Bulatov
# LP relaxation of independent set

(Asked by: username_0 on 2011-02-26)

I've tried the following LP relaxation of maximum independent set

$$\max \sum\_i x\_i$$

$$\text{s.t.}\ x\_i+x\_j\le 1\ \forall (i,j)\in E$$
$$x\_i\ge 0$$

I get $1/2$ for every variable for every cubic non-bipartite graph I tried.

1. Is true for all connected cubic non-bipartite graphs?
2. Is there LP relaxation which works better for such graphs?

**Update 03/05**:

Here's the result of clique-based LP relaxation suggested by Nathan

[![](https://i.sstatic.net/8CJTK.png)](https://i.sstatic.net/8CJTK.png)

I've summarized experiments [here](http://yaroslavvb.blogspot.com/2011/03/linear-programming-for-maximum.html) Interestingly, there seem to be quite a few non-bipartite graphs for which the simplest LP relaxation is integral.

**Tags:** graph-theory, co.combinatorics, linear-programming

> **Comments:**
> **username_1**: The solution $x_i = 1/2$ is certainly not unique. In a cubic bipartite graph, you can have an optimal solution with $x_i = 1$ in one part and $x_i = 0$ in the other part.  
> **username_0**: Sorry, I missed important part, I consider non-bipartite cubic graphs only. Every bipartite cubic graph I tried had an integral solution  
> **username_1**: You also need to add "connected" if you want to avoid non-unique solutions.  
> **username_2**: (1) You forgot to write the nonnegativity constraints.  (2) For bipartite graphs, the optimal value of this LP relaxation is always equal to the maximum size of an independent set.  This is an immediate corollary of [König’s theorem](http://en.wikipedia.org/wiki/K%C3%B6nig%27s_theorem_%28graph_theory%29).  
> **username_3**: @Yaroslav: A side question: how do you draw these graphs?  
> **username_1**: @username_3: Mathematica, I would guess. :)  
> **username_0**: Here Mathematica notebook I used -- http://yaroslavvb.com/upload/save/cstheory-indsetLP.nb  
> **username_4**: @username_0, Sorry for this question, but what's the software you used to drowing graphs?  

---

## 4 answers

### Answer by username_1 on 2011-02-26. Score: 16 | Accepted answer

Non-bipartite connected cubic graphs have the unique optimal solution $x\_i = 1/2$; in a bipartite cubic graph you have an integral optimal solution.

---

*Proof:* In a cubic graph, if you sum over all $3n/2$ constraints $x\_i + x\_j \le 1$, you have $\sum\_i 3 x\_i \le 3n/2$, and hence the optimum is at most $n/2$.

The solution $x\_i = 1/2$ for all $i$ is trivially feasible, and hence also optimal.

In a bipartite cubic graph, each part has half of the nodes, and the solution $x\_i = 1$ in one part is hence also optimal.

Any optimal solution must be tight, that is, we must have $\sum\_i 3 x\_i = 3n/2$ and hence $x\_i + x\_j = 1$ for each edge $\{i,j\}$. Thus if you have an odd cycle, you must choose $x\_i = 1/2$ for each node in the cycle. And then if the graph is connected, this choice gets propagated everywhere.

> **Comments:**
> **username_2**: As I wrote in a comment on the question, you only need the bipartiteness to prove existence of an integral optimal solution (but this requires a different proof from yours).  
> **username_1**: @Tsuyoshi: Yes, König's theorem is good to keep in mind. For example, together with the above observation, it will show that any bipartite cubic graph has a 1-factorisation (i.e., it can be partitioned in three perfect matchings). Of course this is the "wrong" way to prove this result, but I think it nicely demonstrates the power of König's theorem – if you just remember König's theorem, there are lots of classical results in graph theory that you can then re-invent easily.  

---

### Answer by username_5 on 2011-03-01. Score: 12

This LP is half-integral for all graphs, i.e., an optimal solution exists such that each variable is in {0,1/2,1}. It simply follows from a theorem of Nemhauser and Trotter. Of course the same conclusion of half-integrality follows for the LP of the complement problem (vertex cover). When the graph is bipartite the solution is integral. It follows simply from max-flow min-cut theorem or working with extreme point solutions of this LP. Also, the 1/2 edges form an odd-cycle.

Of course, this LP is no good for solving IS problem. Adding Clique constraints or SDPs are a much better approach.

Vertex packings: structural properties and algorithms
GL Nemhauser and Trotter- Math. Program., 1975

> **Comments:**
> **username_1**: Right, see also Theorem 5.6 of [this paper](http://portal.acm.org/citation.cfm?id=365411.365412) for a very simple algorithm that efficiently *finds* a half-integral solution.  
> **username_0**: LP with Clique constraints solved about 50% more graphs from the set above....where can I find SDP formulation?  

---

### Answer by username_8 on 2011-02-27. Score: 7

[Sergiy Butenko's Ph.D thesis](http://etd.fcla.edu/UF/UFE0001011/butenko_s.pdf) from 2003 reviews some other LP relaxations of MIS, as well as some quadratic relaxations.


---

### Answer by username_6 on 2011-02-27. Score: 6

There is another way to get a "relaxed version of maximal independent set". Instead of having as constraints "for each edge, the sum is at most 1", the constraints are "for each complete subgraph, the edge is at most 1". Which means : for each edge, for each triangle, for each $K\_4$ and so on.

This is called the fractional independent set number. You will find some information there :
<http://en.wikipedia.org/wiki/Fractional_coloring>
or in the book "Fractional graph theory" from Daniel Ullman and Edward Scheinerman ( <http://www.ams.jhu.edu/~ers/fgt/> ).

Practically, this formulation is NP-Hard to compute, even though all the variables are continuous --> the number of cliques is exponential, and hard to compute.... But you are free to only enumerate some special cliques, for example just the edges (which you just did), or edges+triangles, or all the cliques up to $K\_k$. After all, the value can only become "more representative" of the real integer value (\*) :-)

Nathann

(\*) this being said, you theoretically hav an arbitrarily large difference between the optimal result in the LP where all the cliques are represented and the optimal independent set

> **Comments:**
> **username_1**: One of the problems with this approach is that if you have a non-bipartite cubic *triangle-free* graph (and there are plenty of those...), the formulation is exactly equal to that in the question, and we have exactly the same bad news. More generally, I think we can always construct graphs in which all nodes are in a $k$-clique and there is no $(k+1)$-clique, and show that $x_i = 1/k$ for all $i$ is the unique optimal solution of the LP.  
> **username_0**: interesting, this seems to be related to easiness of IndependentSet in chordal graphs  
> **username_0**: I did some experiments, and the solution of this LP relaxation was always integral in chordal graphs  
> **username_7**: @YaroslavBulatov There is a reason for your observation. The clique inequalities and nonnegativity bounds provide the convex hull of independent sets if and only if the graph is perfect. Chordal graphs are perfect.  

---

