Primal-Dual Algorithm for Weighted Vertex Cover

The algorithm presented in the preceding section runs in polynomial time, and we have seen that it outputs a vertex cover whose weight is at most twice the weight of the optimum vertex cover, a fact that we express by saying that its approximation factor is $2$.

However, the algorithm needs to solve a linear program and although this can be done in polynomial time, there are much faster ways to compute a vertex cover with approximation factor 2 without solving the linear program. One such algorithm, that we present in this section, is a primal-dual approximation algorithm, meaning that it makes choices guided by the linear program () and its dual but does not actually solve them to optimality.

Let us write the linear programming relaxation of weighted vertex cover once again, along with its dual.

		$$min~~~\sum_{v \in V}w_vx_v$$
		$$s.t.~~~~~ x_u + x_v \geq 1, ~~~\forall e = (u, v) \in E$$
		$$x_v \geq 0 ~~~~ \forall v \in V$$

And, its dual is given as,

		$$max~~~\sum_{e \in E}y_e$$
		$$s.t.~~~~~\sum_{e \in \delta(v)} y_e \leq w_v, ~~~\forall v \in V$$
		$$y_e \geq 0. ~~~~~~~~~~~~~~~~~~~~~~~ \forall e \in E.$$

Here, the notation $\delta(v)$ denotes the set of all edges having $v$ as an endpoint. One may interpret the dual $LP$ variable $y_e$ as prices associated to the edges, and one may interpret $w_v$ as the wealth of vertex $v$. The dual constraint $\sum_{e \in \delta(v)} y_e \leq w_v$ asserts that $v$ has enough wealth to pay for all of the edges incident to it. If edge prices satisfy all the constraints of () then every vertex has enough wealth to pay for its incident edges, and consequently every vertex set $S$ has enough combined wealth to pay for all of the edges covered by $S$. In particular, if $S$ is a vertex cover then the combined wealth of the vertices in $S$ must be at least $\sum_{e\in E} y_e$, which is a manifestation of weak duality: the optimum value of the dual $LP$ is a lower bound on the optimum value of the primal $LP$.

The dual LP insists that we maximize the combined price of all edges, subject to the constraint that each vertex has enough wealth to pay for all the edges it covers. Rather than exactly maximizing the combined price of all edges, we will set edge prices using a natural (but suboptimal) greedy heuristic: go through the edges in arbitrary order, increasing the price of each one as much as possible without violating the dual constraints. This results in the following algorithm.

The variables $s_v$ keep track of the sum $\sum_{e \in \delta(v)} y_e$ (i.e., the left-hand side of the dual constraint corresponding to vertex $v$) as it grows during the execution of the algorithm. The rule for updating $S$ by inserting each vertex $v$ such that $s_v = w_v$ is inspired by the principle of complementary slackness from the theory of linear programming duality: if $x^∗$ is an optimal solution of a primal linear program and $y^∗$ is an optimal solution of the dual, then for every $i$ such that $x_i^* \neq 0$ the $i$th dual constraint must be satisfied with equality by $y^∗$; similarly, for every $j$ such that $y_j^∗ \neq 0$, the $j$th primal constraint is satisfied with equality by $x^∗$. Thus, it is natural that our decisions of which vertices to include in our vertex cover (primal solution) should be guided by keeping track of which dual constraints are tight $(s_v = w_v)$.

It is clear that each iteration of the main loop runs in constant time, so the algorithm runs in linear time. At the end of the loop processing edge $e = (u, v)$, at least one of the vertices $u, v$ must belong to $S$. Therefore, $S$ is a vertex cover. To conclude the analysis we need to prove that the approximation factor is 2. To do so, we note the following loop invariants - statements that hold at the beginning and end of each execution of the for loop, though not necessarily in the middle. Each of them is easily proven by induction on the number of iterations of the for loop.

1. $\mathbf{y}$ is a feasible vector for the dual linear program.
2. $s_v = \sum_{e \in \delta(v)} y_e$.
3. $S = \{v \mid s_v = w_v\}$.
4. $\sum_{v \in V} s_v = 2 \sum_{e \in E} y_e$.

Now the proof of the approximation factor is easy. Recalling that $\sum_{e \in E} y_e \leq \sum_{v \in OPT} w_v$ by week duality, we find that:

$$\sum_{v \in S} w_v = \sum_{v \in S} s_v \leq \sum_{v \in V} s_v = 2\sum_{e \in E} y_e \leq 2\sum_{v \in OPT} w_v.$$ (8.4)