= Solution
Remove the <integer> requirements from the previous formulation to obtain its <linear programming relaxation>. Give each <edge> constraint a nonnegative <dual variable> $y_e$, and each bound for $v\in Z$ a nonnegative <dual variable> $z_v$. Since all right-hand sides are one, the <dual linear program> is
$$
\boxed{\begin{aligned}
\text{minimize}\quad&\sum_{e\in E}y_e+\sum_{v\in Z}z_v\\
\text{subject to}\quad&\sum_{e\ni v}y_e\geq1&&v\in V\setminus Z,\\
&z_v\geq1&&v\in Z,\\
&y_e\geq0,\quad z_v\geq0.
\end{aligned}}
$$
An <integer> <feasible point> selects a multiset of <edges> touching every nonisolated <vertex>, together with at least one singleton for each <isolated vertex>. Repeated <edges> or singleton choices can be discarded without losing coverage, so an optimum has a genuine <edge cover> of the nonisolated part and one singleton per isolated <vertex>. \b[If $G$ has no <isolated vertices>, this is exactly an <edge cover>], with the objective counting selected <edges> including any unnecessary multiplicities. The isolated-singleton extension is necessary because a <graph> with an <isolated vertex> admits no ordinary <edge cover>.
This interpretation concerns <integer> feasible dual solutions. The <linear programming relaxation> can have fractional optima, so its value need not equal the integer <independent set> optimum. For example, the triangle has relaxed independent-set value $3/2$, whereas its maximum <independent set> has size $1$ and its minimum <edge cover> has size $2$.
Back to article page
