13.1.1. Vertex Cover

Consider the weighted vertex cover problem, where we are given a graph \(G\) and a weight function \(w : V \rightarrow \mathbb{R}^+\) and our goal is to pick a minimum-weight subset of vertices \(C \subseteq V\) such that every edge of \(G\) has at least one endpoint in \(C\). The ILP formulation of this problem is

\[\begin{gathered} \text{Minimize } \sum_{v \in V} w_vx_v\\ \begin{aligned} \text{s.t. } x_u + x_v &\ge 1 && \forall (u,v) \in E\\ x_v &\in \{0,1\} && \forall v \in V. \end{aligned} \end{gathered}\tag{13.1}\]

Its LP relaxation is

\[\begin{gathered} \text{Minimize } \sum_{v \in V} w_vx_v\\ \begin{aligned} \text{s.t. } x_u + x_v &\ge 1 && \forall (u,v) \in E\\ x_v &\ge 0 && \forall v \in V. \end{aligned} \end{gathered}\tag{13.2}\]

An extreme-point solution of an LP is a feasible solution \(\hat x\) that cannot be expressed as the linear combination \(\hat x = \lambda \hat y + (1 - \lambda) \hat z\) of two distinct feasible solutions \(\hat y\) and \(\hat z\) of the LP. Intuitively, this means that the solution \(\hat x\) is a corner of the feasible region of the LP. The Simplex Algorithm finds an optimal extreme-point solution to any LP it is given but is not guaranteed to run in polynomial time. Interior-point methods, which run in polynomial time, do not necessarily find extreme-point solutions. However, given an arbitrary optimal solution, an optimal extreme-point solution can be found efficiently. We do not discuss how this is done here but assume that we can find an optimal extreme-point solution to an LP in polynomial time.

Lemma 13.1: An extreme-point solution of (13.2) satisfies \(\hat x_v \in \bigl\{ 0, \frac{1}{2}, 1 \bigr\}\) for all \(v \in V\).

Proof: Consider a feasible solution \(\hat x\) of (13.2) that has a vertex \(v \in V\) with \(\hat x_v \notin \bigl\{ 0, \frac{1}{2}, 1 \bigr\}\). We prove that \(\hat x\) is not an extreme-point solution.

Define two solutions \(\hat y\) and \(\hat z\) as

\[\hat y_v = \begin{cases} \hat x_v - \epsilon & \text{if } 0 < \hat x_v < \frac{1}{2}\\ \hat x_v + \epsilon & \text{if } \frac{1}{2} < \hat x_v < 1\\ \hat x_v & \text{otherwise} \end{cases}\]

and

\[\hat z_v = \begin{cases} \hat x_v + \epsilon & \text{if } 0 < \hat x_v < \frac{1}{2}\\ \hat x_v - \epsilon & \text{if } \frac{1}{2} < \hat x_v < 1\\ \hat x_v & \text{otherwise} \end{cases}.\]

Since there exists a vertex \(v \in V\) with \(\hat x_v \notin \bigl\{ 0, \frac{1}{2}, 1 \bigr\}\), we have \(\hat y \ne \hat z\). Moreover, \(\hat x = \frac{\hat y}{2} + \frac{\hat z}{2}\), that is, it is not an extreme-point solution if \(\hat y\) and \(\hat z\) are feasible. Thus, we need to prove that \(\hat y\) and \(\hat z\) are feasible solutions of (13.2).

Since \(0 < \hat x_v < 1\) for all \(v \in V\) such that \(\hat y_v \ne \hat x_v\) and \(\hat z_v \ne \hat x_v\), we can choose \(\epsilon > 0\) small enough to ensure that \(0 \le \hat y_v, \hat z_v \le 1\) for all \(v \in V\).

For any edge \((u, v) \in E\), we have \(\hat x_u + \hat x_v \ge 1\) because \(\hat x\) is a feasible solution. If \(\hat x_u + \hat x_v > 1\), we can once again choose \(\epsilon > 0\) small enough to ensure that \(\hat y_u + \hat y_v \ge 1\) and \(\hat z_u + \hat z_v \ge 1\). If \(\hat x_u + \hat x_v = 1\), then assume w.l.o.g. that \(\hat x_u \le \hat x_v\). This implies that \(\hat x_u = \hat x_v = \frac{1}{2}\), \(\hat x_u = 0\) and \(\hat x_v = 1\), or \(0 < \hat x_u < \frac{1}{2}\) and \(\frac{1}{2} < \hat x_v < 1\). In all three cases \(\hat y_u + \hat y_v = \hat z_u + \hat z_v = \hat x_u + \hat x_v = 1\). Thus, \(\hat y\) and \(\hat z\) are feasible solutions and \(\hat x\) is not an extreme-point solution. ▨

By Lemma 13.1, we can obtain a polynomial-time \(2\)-approximation for the vertex cover problem by computing an extreme-point solution \(\hat x\) of (13.2) and adding all vertices \(v \in V\) to a vertex cover \(C\) that satisfy \(\hat x_v > 0\). The resulting set \(C\) is represented by the vector \(\tilde x\) defined as

\[\tilde x_v = \begin{cases} 1 & \text{if } \hat x_v > 0\\ 0 & \text{if } \hat x_v = 0 \end{cases}\]

for all \(v \in V\). This implies that \(\tilde x_u + \tilde x_v \ge \hat x_u + \hat x_v \ge 1\) for every edge \((u, v) \in E\), that is, \(C\) is valid vertex cover. By the half-integrality of \(\hat x\), we have \(\hat x_v \ge \frac{1}{2}\) for every vertex \(v \in V\) such that \(\tilde x_v = 1\). Thus, \(\tilde x_v \le 2 \hat x_v\) for all \(v \in V\) and

\[w(C) = \sum_{v \in V} w_v\tilde x_v \le 2 \sum_{v \in V} w_v \hat x_v = 2 \cdot \mathrm{OPT}_f \le 2 \cdot \mathrm{OPT},\]

that is, \(C\) is a \(2\)-approximation of an optimal vertex cover.

In this example, I focused on the half-integrality of the vertex cover problem to illustrate this remarkable property using a simple example. As the following exercise asks you to prove,half-integrality is not essential to obtain a \(2\)-approximation of an optimal vertex cover via LP rounding:

Exercise 13.1: Let \(\hat x\) be an optimal solution of the LP relaxation (13.2) of the ILP formulation (13.1) of the vertex cover problem, and let

\[\tilde x_v = \begin{cases} 1 & \text{if } \hat x_v \ge \frac{1}{2}\\ 0 & \text{if } \hat x_v < \frac{1}{2}. \end{cases}\]

Prove that \(\tilde x\) is a feasible solution of (13.1) with objective function value no greater than \(2 \cdot \mathrm{OPT}_f\).