<p>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
<span class="math-container">$$\begin{align*}
0\le x_i&amp;\le1,&amp;&amp;i\in V,\\
x_i+x_j&amp;\le1,&amp;&amp;\{i,j\}\in E,
\end{align*}$$</span>
hence the vertex is defined by the equations
<span class="math-container">$$\begin{align*}
x_i&amp;=0,&amp;&amp;i\in V_0,\\
x_i&amp;=1,&amp;&amp;i\in V_1,\\
x_i+x_j&amp;=1,&amp;&amp;\{i,j\}\subseteq E'
\end{align*}$$</span>
for some <span class="math-container">$V_0,V_1\subseteq V$</span> and <span class="math-container">$E'\subseteq E$</span>, such that this system has a unique solution. Now, the latter immediately implies that <span class="math-container">$x_i\in\{0,1/2,1\}$</span>: if <span class="math-container">$\vec x$</span> is any solution, then <span class="math-container">$\vec x'$</span> defined by
<span class="math-container">$$x'_i=\begin{cases}
x_i,&amp;\text{if }x_i\in\{0,1\},\\
1-x_i,&amp;\text{if }0&lt;x_i&lt;1
\end{cases}$$</span>
is also a valid solution, hence <span class="math-container">$\vec x=\vec x'$</span> by uniqueness.</p>

<p>Moreover, if the graph is bipartite with partitions <span class="math-container">$A$</span> and <span class="math-container">$B$</span>, then
<span class="math-container">$$x''_i=\begin{cases}
x_i,&amp;\text{if }x_i\in\{0,1\},\\
0,&amp;\text{if }0&lt;x_i&lt;1\text{ and }i\in A,\\
1,&amp;\text{if }0&lt;x_i&lt;1\text{ and }i\in B
\end{cases}$$</span>
is also a valid solution, hence <span class="math-container">$x_i\in\{0,1\}$</span>.</p>

CC BY-SA 4.0
2020-06-02T15:51:08.400Z
Nice proof, thank you.
Neal Young
CC BY-SA 4.0
2020-06-03T14:35:41.347Z
So $V_0, V_1$ are sets that represent values of vertices with values $0$ and $1$ respectively? I still don't know how $x_i+x_j=1, \{i,j\}\subseteq E'$ implies values $\{0,1/2,1\}$
Jakub Jabłoński
CC BY-SA 4.0
2020-06-03T17:21:29.190Z
You need the additional property that the linear system has a unique solution to imply values in $\{0,1/2,1\}$.
Emil Jeřábek
CC BY-SA 4.0
2020-06-04T19:40:19.247Z
Jakub, the argument for that is in the proof given in the answer, following *"the latter immediately implies that $x_i\in\{0, 1/2, 1\}$:"*  And e.g. $V_0$ is defined as *the set of vertices $i$ for which the equation $x_i=0$ is in the set of equations that defines the vertex of the polytope*.  That is not (a-priori) the same as the set of vertices for which $x_i$ is $0$, because conceivably $x_i$ could be $0$ even though that is not one of the defining equations.  (Although the rest of the proof establishes that that cannot happen.)
Neal Young
CC BY-SA 4.0
2020-06-07T12:37:02.200Z
I can't understand why the latter (which I suppose refers to $E'\subseteq E$) immediately implies that. Supposing possible values are $0,1/3,2/3,1$, it would still satisfy the equations.
Jakub Jabłoński
CC BY-SA 4.0
2020-06-07T14:20:24.903Z
This cannot happen because then the solution would not be unique.
Emil Jeřábek
CC BY-SA 4.0
2020-08-25T13:25:13.433Z
But where does the uniqueness of the solution come from? My first thought is that if there are multiple optimal solutions, why can't I narrow it to only one as the only thing that matters is output value (independent set), not values of variables. So in this case, this assumption doesn't affect the value of the solution of this LP problem.
Jakub Jabłoński
CC BY-SA 4.0
2020-08-25T14:40:48.977Z
Once again, slowly. The optimal value of the original LP is attained at a **VERTEX** of the polytope. Fix that vertex $x$. It is a basic fact of polyhedral geometry that every vertex $x$ is an intersection of bounding hyperplanes of the polytope. That is, there **EXISTS** a linear system $S$ whose unique solution is $x$, such that every linear equations in $S$ is obtained from some inequality of the original LP by replacing $\le$ with $=$. Fix such $S$. In the specific case discussed here, $S$ has the form given in my answer. It has a unique solution because **WE CHOSE IT** that way.
Emil Jeřábek
CC BY-SA 4.0
2020-09-09T17:34:54.627Z
But when considering triangle graph, each of the vertices can have $1/3$, that's a valid, optimal solution. According to the answer, $0$ and $1$ values remain, but there are none of them and for the rest $1-x$ is applied. In case of this graph, it will result in values $2/3$, which isn't valid solution, because in triangle max independent set both relaxed and not is equal to 1, not $3*2/3$, which is 2.
Jakub Jabłoński
CC BY-SA 4.0
2020-09-10T10:17:13.173Z
No. The (unique) optimal solution for the triangle graph gives $1/2$ to each vertex, with total value $3/2$.
Emil Jeřábek
CC BY-SA 4.0
2020-09-10T20:15:20.107Z
Okay. I just found the issue. Mine definition has additional condition, that for clique of size $n$ $\sum_i v_i \leq 1$
Jakub Jabłoński
CC BY-SA 4.0
2020-09-18T11:23:30.630Z
Considering $K_4$ graph without 1 edge. You can assign it two values of $1/3$ and two values of $2/3$, which is valid unique solution (a vertex). However for each of them performing $1-x_i$ as in your answer, this solution will no longer be valid, as there will be edge in which values sum to $4/3$
Jakub Jabłoński
CC BY-SA 4.0
2020-09-18T12:05:25.693Z
No, that’s not a vertex, as it is a proper convex combination of the solutions $(0,0,1,1)$ and $(1/2,1/2,1/2,1/2)$. And I’m getting quite fed up by these pointless comments. I’m not going to respond further unless you bring something substantial. If you still don’t understand my answer, ask your supervisor or at https://math.stackexchange.com .
Emil Jeřábek
CC BY-SA 4.0
2020-06-02T13:35:05.463Z
2020-06-02T13:48:12.193Z
2020-06-02T13:48:12.193Z
Emil Jeřábek
<p>This is discussed in a related cstheory post:</p>

<p><a href="https://cstheory.stackexchange.com/questions/5170/lp-relaxation-of-independent-set">LP relaxation of independent set</a></p>

<p>That post cites this publication:</p>

<p>[1] Nemhauser, G.L., Trotter, L.E. Vertex packings: Structural properties and algorithms. Mathematical Programming 8, 232–248 (1975). <a href="https://doi.org/10.1007/BF01580444" rel="nofollow noreferrer">https://doi.org/10.1007/BF01580444</a></p>

<p>That publication in turn cites a few others, including these:</p>

<p>[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. <a href="https://doi.org/10.2307/j.ctt13x0wct.16" rel="nofollow noreferrer">https://doi.org/10.2307/j.ctt13x0wct.16</a></p>

<p>[3] Nemhauser, G.L., Trotter, L.E. Properties of vertex packing and independence system polyhedra. Mathematical Programming 6, 48–61 (1974). <a href="https://doi.org/10.1007/BF01580222" rel="nofollow noreferrer">https://doi.org/10.1007/BF01580222</a></p>

<p>[4] Leslie Earl Trotter. 1973. Solution characteristics and algorithms for the vertex packing problem. Ph.D. Dissertation. Cornell University, USA. Order Number: AAI7406323.</p>

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

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

CC BY-SA 4.0
2020-06-02T13:03:00.227Z
2020-06-02T13:03:00.227Z
Neal Young
<p>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 <span class="math-container">${ \{0,0.5,1 \} }$</span>. I'm looking for proof of that. </p>

<p>Someone in this topic <a href="https://cstheory.stackexchange.com/questions/5170/lp-relaxation-of-independent-set">LP relaxation of independent set</a>  seems to make use of it.</p>

<p>And here <a href="http://www-sop.inria.fr/members/Frederic.Havet/Cours/fractional.pdf" rel="nofollow noreferrer">http://www-sop.inria.fr/members/Frederic.Havet/Cours/fractional.pdf</a> is a proof for vertex-cover, which is close, but nothing is mentioned about independent set.</p>

<p>Does anyone know a proof of that?</p>

<reference-request><graph-theory><linear-programming><independent-set>
Proof that optimal solutions of LP Relaxation of independent set are half-integral
Jakub Jabłoński
# Proof that optimal solutions of LP Relaxation of independent set are half-integral

(Asked by: username_0 on 2020-05-31)

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](https://cstheory.stackexchange.com/questions/5170/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?

**Tags:** reference-request, graph-theory, linear-programming, independent-set

---

## 2 answers

### Answer by username_1 on 2020-06-02. Score: 2

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
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
is also a valid solution, hence $x\_i\in\{0,1\}$.

> **Comments:**
> **username_2**: Nice proof, thank you.  
> **username_0**: So $V_0, V_1$ are sets that represent values of vertices with values $0$ and $1$ respectively? I still don't know how $x_i+x_j=1, \{i,j\}\subseteq E'$ implies values $\{0,1/2,1\}$  
> **username_1**: You need the additional property that the linear system has a unique solution to imply values in $\{0,1/2,1\}$.  
> **username_2**: Jakub, the argument for that is in the proof given in the answer, following *"the latter immediately implies that $x_i\in\{0, 1/2, 1\}$:"*  And e.g. $V_0$ is defined as *the set of vertices $i$ for which the equation $x_i=0$ is in the set of equations that defines the vertex of the polytope*.  That is not (a-priori) the same as the set of vertices for which $x_i$ is $0$, because conceivably $x_i$ could be $0$ even though that is not one of the defining equations.  (Although the rest of the proof establishes that that cannot happen.)  
> **username_0**: I can't understand why the latter (which I suppose refers to $E'\subseteq E$) immediately implies that. Supposing possible values are $0,1/3,2/3,1$, it would still satisfy the equations.  
> **username_1**: This cannot happen because then the solution would not be unique.  
> **username_0**: But where does the uniqueness of the solution come from? My first thought is that if there are multiple optimal solutions, why can't I narrow it to only one as the only thing that matters is output value (independent set), not values of variables. So in this case, this assumption doesn't affect the value of the solution of this LP problem.  
> **username_1**: Once again, slowly. The optimal value of the original LP is attained at a **VERTEX** of the polytope. Fix that vertex $x$. It is a basic fact of polyhedral geometry that every vertex $x$ is an intersection of bounding hyperplanes of the polytope. That is, there **EXISTS** a linear system $S$ whose unique solution is $x$, such that every linear equations in $S$ is obtained from some inequality of the original LP by replacing $\le$ with $=$. Fix such $S$. In the specific case discussed here, $S$ has the form given in my answer. It has a unique solution because **WE CHOSE IT** that way.  
> **username_0**: But when considering triangle graph, each of the vertices can have $1/3$, that's a valid, optimal solution. According to the answer, $0$ and $1$ values remain, but there are none of them and for the rest $1-x$ is applied. In case of this graph, it will result in values $2/3$, which isn't valid solution, because in triangle max independent set both relaxed and not is equal to 1, not $3*2/3$, which is 2.  
> **username_1**: No. The (unique) optimal solution for the triangle graph gives $1/2$ to each vertex, with total value $3/2$.  
> **username_0**: Okay. I just found the issue. Mine definition has additional condition, that for clique of size $n$ $\sum_i v_i \leq 1$  
> **username_0**: Considering $K_4$ graph without 1 edge. You can assign it two values of $1/3$ and two values of $2/3$, which is valid unique solution (a vertex). However for each of them performing $1-x_i$ as in your answer, this solution will no longer be valid, as there will be edge in which values sum to $4/3$  
> **username_1**: No, that’s not a vertex, as it is a proper convex combination of the solutions $(0,0,1,1)$ and $(1/2,1/2,1/2,1/2)$. And I’m getting quite fed up by these pointless comments. I’m not going to respond further unless you bring something substantial. If you still don’t understand my answer, ask your supervisor or at https://math.stackexchange.com .  

---

### Answer by username_2 on 2020-06-02. Score: 1

This is discussed in a related cstheory post:

[LP relaxation of independent set](https://cstheory.stackexchange.com/questions/5170/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.


---

