Problem

Given an undirected graph G=<V,E>G = \left<V, E \right> in which each vertex ii is associated with a weight wiw_i, the vertex cover problem asks for the subset of vertices with minimum weight, such that every edge in GG is incident to at least one vertex in the set.

The problem can be formulate as integer program then relaxed as linear program. Let nn and mm be the number of vertices and edges respectively. For every vertex i∈[n]i \in [n], there is a indicator variable xi∈[0,1]x_i \in [0, 1]. The linear program is given as

min⁡∑i=1nwixis.t.xi+xj≥1∀(i,j)∈Exi≥0∀i∈[n] \begin{array}{llr} \min & \sum_{i = 1}^n w_i x_i &\\ \text{s.t.} & x_i + x_j \ge 1 & \forall (i,j) \in E \\ & x_i \ge 0 & \forall i \in [n] \end{array}

Its dual is given by

max⁡∑(i,j)∈Eyi,js.t.∑(i,j)∈Eyi,j≤wi∀i∈[n]yi,j≥0∀(i,j)∈E \begin{array}{llr} \max & \sum_{(i,j) \in E} y_{i,j} &\\ \text{s.t.} & \sum_{(i, j) \in E} y_{i, j} \le w_i & \forall i \in [n] \\ & y_{i, j} \ge 0 & \forall (i, j) \in E \end{array}

where yi,jy_{i,j} and yj,iy_{j, i} denote the same variable.

By weak duality,

∑(i,j)∈Eyi,j≤∑(i,j)∈E(xi+xj)yi,j=∑i=1n(∑(i,j)∈Eyi,j)xi≤∑i=1nwixi \sum_{(i, j) \in E} y_{i, j} \le \sum_{(i,j) \in E} (x_i + x_j ) y_{i, j} = \sum_{i = 1}^n \left( \sum_{(i, j) \in E} y_{i, j}\right) x_i \le \sum_{i = 1}^n w_i x_i

Let x∗x^* and y∗y^* denotes the primal and dual optimal solutions respectively. By strong duality, the complementary slackness states that

xi∗+xj∗=1∨yi,j∗=0(1)∑(i,j)∈Eyi,j∗=wi∨xi∗=0(2) \begin{array}{llllr} x_i^* + x_j^* = 1 &\vee & y_{i, j}^* = 0 && (1)\\ \sum_{(i, j) \in E} y^*_{i, j} = w_i &\vee & x^*_i = 0 && (2) \end{array}

Now we show how to use this condition to construct an approximate primal solution. We begin with an initial values of x=(0,0,...,0)x = (0, 0, ..., 0) and y=(0,0,...,0)y = (0, 0, ..., 0). Note that yy is a dual feasible solution and condition (2)(2) holds. However xx is not a primal feasible solution. In the following we give an algorithm that maintains the feasibility of yy and condition (2)(2) while restores the feasibility of xx.

Algorithm 1 -- an 2 approximation algorithm
while ∃(i,j)∈E,s.t.,xi+xj<1\exists (i, j) \in E, s.t., x_i + x_j < 1
\quad increase yi,jy_{i, j} as much as possible until either

1.∑(i,k)∈Eyi,k=wi1. \quad \sum_{(i, k) \in E} y_{i, k} = w_i, then set xi=1x_i = 1
2.∑(j,k)∈Eyj,k=wj2. \quad \sum_{(j, k) \in E} y_{j, k} = w_j, then set xj=1x_j = 1

Note that in the inner loop, if two conditions hold simultaneously, we need only set one of xix_i and xjx_j to 1.

Now we analyze the algorithm. It is apparent that ∑(i,j)∈Eyi,j≤wi∀i∈[i]\sum_{(i, j) \in E} y_{i,j} \le w_i \forall i \in [i] holds throughout the algorithm. Moreover, for i∈[i]i \in [i], xi=0x_i = 0 or xi=1x_i = 1. In the latter case, we must have ∑(i,k)∈Eyi,k=wi\sum_{(i, k) \in E} y_{i, k} = w_i. We conclude that when the algorithm terminates,

∑(i,j)∈Eyi,j≤∑i=1nwixi=∑i=1n(∑(i,j)∈Eyi,j)xi=∑(i,j)∈E(xi+xj)yi,j \sum_{(i, j) \in E} y_{i, j} \le \sum_{i = 1}^n w_i x_i = \sum_{i = 1}^n \left( \sum_{(i, j) \in E} y_{i, j}\right) x_i = \sum_{(i,j) \in E} (x_i + x_j ) y_{i, j}

But xi+xjx_i + x_j is at most 22, therefore ∑(i,j)∈Eyi,j≤∑i=1nwixi≤2∑(i,j)∈Eyi,j\sum_{(i, j) \in E} y_{i, j} \le \sum_{i = 1}^n w_i x_i \le 2\sum_{(i, j) \in E} y_{i, j}.