LP Rounding Algorithm for Weighted Vertex Cover

In an undirected graph $G = (V, E)$, if $S \subseteq V$ is a set of vertices and $e$ is an edge, we say that $S$ covers $e$ if at least one endpoint of $e$ belongs to $S$. We say that $S$ is a vertex cover if it covers every edge. In the weighted vertex cover problem, one is given an undirected graph $G = (V, E)$ and a weight $w_v \geq 0$ for each vertex $v$, and one must find a vertex cover of minimum combined weight.

We can express the weighted vertex cover problem as an integer program, by using decision variables $x_v$ for all $v \in V$ that encode whether $v \in S$. For any set $S \subseteq V$ we can define a vector $\mathbf{x}$, with components indexed by vertices of $G$, by specifying that,

$S$ is a vertex cover if and only if the constraint $x_u + x_v \geq 1$ is satisfied for every edge $e = (u, v)$. Conversely, if $x \in \{0, 1\}^V$ satisfies $x_u + x_v \geq 1$ for every edge $e = (u, v)$ then the set $S = \{v \mid x_v = 1\}$ is a vertex cover. Thus, the weighted vertex cover problem can be expressed as the following integer program.

		$$min~~~\sum_{v \in V}w_vx_v ~~~~~$$(minimize the total weight)
		$$s.t.~~~~~~x_u + x_v \geq 1, ~~~\forall e = (u, v) \in E ~~~~~$$(cover every edge of the graph)
		$$x_v \in \{0, 1\}~~~~ \forall v \in V ~~~~$$   (every vertex is either in vertex cover or not)

To design an approximation algorithm for weighted vertex cover, we will transform this integer program into a linear program by relaxing the constraint $x_v \in \{0, 1\}$ to allow the variables $x_v$ to take fractional values.

		$$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$$

It may seem more natural to replace the constraint $x_v \in \{0, 1\}$ with $x_v \in [0, 1]$ rather than $x_v \geq 0$, but the point is that an optimal solution of the linear program will never assign any of the variables $x_v$ a value strictly greater than $1$, because the value of any such variable could always be reduced to $1$ without violating any constraints, and this would only improve the objective function $\sum_v w_v x_v$. Thus, writing the constraint as $x_v \geq 0$ rather than $x_v \in [0, 1]$ is without loss of generality.

It is instructive to present an example of a fractional solution of equation () that achieves a strictly lower weight than any integer solution. One such example is when $G$ is a 3-cycle with vertices $u, v, w$, each having weight $1$. Then the vector $\mathbf{x} = (\frac{1}{2}, \frac{1}{2}, \frac{1}{2})$ satisfies all of the constraints of () and the objective function evaluates to $\frac{3}{2}$ at $\mathbf{x}$. In contrast, the minimum weight of a vertex cover of the 3-cycle is $2$.

We can solve the linear program () in polynomial time, but as we have just seen, the solution may be fractional. In that case, we need to figure out how we are going to post-process the fractional solution to obtain an actual vertex cover. In this case, the natural idea of rounding to the nearest integer works. Let $\mathbf{x}$ be an optimal solution of the linear program () and define:

Now let $S = \{v \mid \bar{x}_v = 1\}$. Note that $S$ is a vertex cover because for every edge $e = (u, v)$ the constraint $x_u + x_v \geq 1$ implies that at least one of $x_u, x_v$ is greater than or equal to $1/2$.

Finally, we the analyze the approximation ratio of this algorithm. We observe that the rounding rule () has the property that for all $v$,

$$\bar{x}_v \leq 2x_v.$$

Let $S$ denote the vertex cover chosen by our $LP$ rounding algorithm, and let $OPT$ denote the optimum vertex cover, we have

$$\sum_{v \in S}w_v = \sum_{v \in V} w_v\bar{x}_v \leq 2\sum_{v \in V} w_vx_v \leq 2\sum_{v \in OPT} w_v,$$ (8.3)

where the final inequality holds because the fractional optimum of the linear program () must be less than or equal to the optimum of the integer program () because its feasible region is at least as big.