-2
$\begingroup$

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?

$\endgroup$
0

2 Answers 2

2
$\begingroup$

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\}$.

$\endgroup$
13
  • $\begingroup$ Nice proof, thank you. $\endgroup$
    – Neal Young
    Jun 2, 2020 at 15:51
  • $\begingroup$ 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\}$ $\endgroup$ Jun 3, 2020 at 14:35
  • $\begingroup$ You need the additional property that the linear system has a unique solution to imply values in $\{0,1/2,1\}$. $\endgroup$ Jun 3, 2020 at 17:21
  • $\begingroup$ 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.) $\endgroup$
    – Neal Young
    Jun 4, 2020 at 19:40
  • $\begingroup$ 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. $\endgroup$ Jun 7, 2020 at 12:37
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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