Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I saw somewhere that optimal solutions of LP Relaxation of independent set are half-integral, by what I mean the possible values of a solution are ${ \{0,0.5,1 \} }$. I'm looking for proof of that.
Someone in this topic LP relaxation of independent set seems to make use of it.
And here http://www-sop.inria.fr/members/Frederic.Havet/Cours/fractional.pdf is a proof for vertex-cover, which is close, but nothing is mentioned about independent set.
Does anyone know a proof of that?
The LP in question is a maximization over a bounded polytope, hence the optimal value is attained at a vertex of the polytope. Moreover, any vertex can be described as a unique solution of a system of linear equations obtained by replacing inequalities with equalities in a subset of the inequalities defining the problem. Here, the polytope is defined by $$\begin{align*} 0\le x_i&\le1,&&i\in V,\\ x_i+x_j&\le1,&&\{i,j\}\in E, \end{align*}$$ hence the vertex is defined by the equations $$\begin{align*} x_i&=0,&&i\in V_0,\\ x_i&=1,&&i\in V_1,\\ x_i+x_j&=1,&&\{i,j\}\subseteq E' \end{align*}$$ for some $V_0,V_1\subseteq V$ and $E'\subseteq E$, such that this system has a unique solution. Now, the latter immediately implies that $x_i\in\{0,1/2,1\}$: if $\vec x$ is any solution, then $\vec x'$ defined by $$x'_i=\begin{cases} x_i,&\text{if }x_i\in\{0,1\},\\ 1-x_i,&\text{if }0<x_i<1 \end{cases}$$ is also a valid solution, hence $\vec x=\vec x'$ by uniqueness.
Moreover, if the graph is bipartite with partitions $A$ and $B$, then $$x''_i=\begin{cases} x_i,&\text{if }x_i\in\{0,1\},\\ 0,&\text{if }0<x_i<1\text{ and }i\in A,\\ 1,&\text{if }0<x_i<1\text{ and }i\in B \end{cases}$$ is also a valid solution, hence $x_i\in\{0,1\}$.
This is discussed in a related cstheory post:
LP relaxation of independent set
That post cites this publication:
[1] Nemhauser, G.L., Trotter, L.E. Vertex packings: Structural properties and algorithms. Mathematical Programming 8, 232–248 (1975). https://doi.org/10.1007/BF01580444
That publication in turn cites a few others, including these:
[2] Balinski, M. (1970). ON MAXIMUM MATCHING, MINIMUM COVERING AND THEIR CONNECTIONS. In KUHN H. (Ed.), Proceedings of the Princeton Symposium on Mathematical Programming (pp. 303-312). Princeton, New Jersey: Princeton University Press. https://doi.org/10.2307/j.ctt13x0wct.16
[3] Nemhauser, G.L., Trotter, L.E. Properties of vertex packing and independence system polyhedra. Mathematical Programming 6, 48–61 (1974). https://doi.org/10.1007/BF01580222
[4] Leslie Earl Trotter. 1973. Solution characteristics and algorithms for the vertex packing problem. Ph.D. Dissertation. Cornell University, USA. Order Number: AAI7406323.
You can look through these. From a quick scan of the first three it didn't seem obvious which contained a proof. If I recall, one can prove that for bipartite graphs there are optimal integer solutions (by considering the underlying max flow problem), and then, to prove the existence of a half-integral optimum for any general graph, convert it into a bipartite graph by making two copies of each node in a natural way and applying the result for bipartite graphs. Maybe there are simpler ways to go about it.
BTW, this kind of reference request, which you can answer yourself by taking some time to do a web search, is probably not an appropriate question for this forum, which is for research-level questions in TCS.
