LP relaxation of independent set

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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

Answer 4

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