Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

I've summarized experiments here Interestingly, there seem to be quite a few non-bipartite graphs for which the simplest LP relaxation is integral.

share|improve this question
    
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 Feb 26 '11 at 22:00
1  
Sorry, I missed important part, I consider non-bipartite cubic graphs only. Every bipartite cubic graph I tried had an integral solution –  Yaroslav Bulatov Feb 26 '11 at 22:06
    
You also need to add "connected" if you want to avoid non-unique solutions. –  Jukka Suomela Feb 26 '11 at 22:08
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‌​. –  Tsuyoshi Ito Feb 26 '11 at 22:22
2  
@Yaroslav: A side question: how do you draw these graphs? –  Tim Feb 27 '11 at 2:01
show 3 more comments

4 Answers

up vote 14 down vote accepted

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.

share|improve this answer
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). –  Tsuyoshi Ito Feb 27 '11 at 1:46
    
@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 Feb 27 '11 at 10:25
add comment

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

share|improve this answer
    
Right, see also Theorem 5.6 of this paper for a very simple algorithm that efficiently finds a half-integral solution. –  Jukka Suomela Mar 1 '11 at 16:34
    
LP with Clique constraints solved about 50% more graphs from the set above....where can I find SDP formulation? –  Yaroslav Bulatov Mar 1 '11 at 19:22
add comment

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

share|improve this answer
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. –  Jukka Suomela Feb 27 '11 at 10:32
    
interesting, this seems to be related to easiness of IndependentSet in chordal graphs –  Yaroslav Bulatov Feb 28 '11 at 6:13
    
I did some experiments, and the solution of this LP relaxation was always integral in chordal graphs –  Yaroslav Bulatov Mar 1 '11 at 8:40
    
@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 Dec 17 '13 at 3:13
add comment

Sergiy Butenko's Ph.D thesis from 2003 reviews some other LP relaxations of MIS, as well as some quadratic relaxations.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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