# Finding integrality gap for maximum weight independent set

One of the exercises I was given was to formulate Integer Linear Program (ILP) and relaxed version of it (LP) to solve the maximum weight independent set, and I need to find an integrality gap of my LP relaxation.

As far as my knowledge goes, integrality gap for maximization problem is the the maximum ratio cost(LP)/cost(ILP) over all instances of a problem. But I've been googling for a little bit, and most examples only showed how to get a lower bound of integrality gap by taking some arbitrary instance. Is it possible to get an exact ratio?

Suppose you prove that an upper bound on the integrality gap is $\alpha$. The goal is to “create” an instance (weighted graph, or better yet, a family of weighted graphs) where the value of the optimal LP solution is $\alpha$ times the value of the ILP solution.
Independent set ILP $$O_{ILP}=\max\sum_{v\in V}x_{v}\cdot w(v)$$
$$x_{v}+x_{u} \leq 1\ \ \ \forall u,v\in V$$ $$x_{v}\in\{0,1\} \ \ \forall v\in V$$
The relaxation is straight forward. say the value of the optimal solution to the LP is $O_{LP}.$ Now, you want to upper bound $O_{LP}/O_{ILP}.$ To do this, try to consider a rounding scheme that converts a solution for the LP into a feasible solution for the corresponding ILP. One such scheme involves reasoning about the constraints, that is $x_{v}+x_{u}\leq1$ for every edge in G. This implies that at least one of $x_{u}$ or $x_{v}$ is atleast $1/2$, and therefore all vertices in $v\in V$ such that $x_{v}>\frac{1}{2}$ is an independent set in $G$. I'll leave it to you to reason about how to compare $O_{LP}$ and $O_{ILP}$, (i.e. determine the maximum of the ratio $\alpha=\max O_{LP}/O_{ILP}$), and to find an instance where $O_{LP}$ is atleast $\alpha.$
• I guess if you have all vertices in a graph assigned weight exactly 1/2 by the LP, then you will have issues since no edge constraint would be violated. So consider the complete graph and assign whatever values you want to the vertices (say each has weight $M$ in the graph) then $O_{LP}$ is $(n \cdot M)/2$ but $OPT_{ILP}=M$ so the integrality gap is actually $n/2$. – mm8511 Nov 25 '17 at 22:41