Maximum independent set relaxation and its dual

combinatoricsgraph theoryinteger programminglinear programming

The integer program for the independent set is given by

\begin{align*}
&\max\sum_{v\in V}x_v\\
&\text{s.b.t } x_u+x_v\leq 1, \text{ for all }\{u,v\}\in E\\
&\quad\quad \ x_v\in\{0,1\}, \text{ for all }v\in V
\end{align*}

So, the relaxation should be $0\leq x_v\leq 1$. However, many write $x_v\geq 0$, probably because $x_u+x_v\leq 1$ implies that $x_u,x_v\leq 1$ for all $\{u,v\}\in E$. However, if there are isolated vertices then the LP relaxation is unbounded which feels a bit wrong.

For the dual program, adding $x_i\leq 1$ causes introducing the additional dual variable $y_v$ resulting
\begin{align*}
&\min\sum_{e\in E}y_{e}+\sum_{v\in V}y_i\\
&\text{s.b.t } \sum_{e\in E\colon v\in e} y_{e}\geq 1 &\text{for all }v\in V\\
& &y_e\geq 0, \text{ for all }e\in E\\
& &y_v\geq 1, \text{ for all }v\in E
\end{align*}

However, it complicates the deriving that the dual of the maximum independent set is the minimum edge cover, as derived here (at Problem 3).

If you can spot an error, or explain how it makes sense it will be helpful.

Best Answer

You have an error in the dual objective: $y_i$ versus $y_v$

Your dual constraint needs to include the new dual variable.

The lower bound on the new dual variable should be $0$ instead of $1$.

Also, it would be less confusing to give the new dual variable a new name because you are already using $y$.

Related Question