Past exam of the computer science course of the University of Oxford / 2018 / Algorithms / 3 / c / 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 isAn 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. 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$.