Vertex Cover Problem

In the mathematical discipline of graph theory, a vertex cover (sometimes node cover) of a graph is a set of vertices that includes at least one endpoint of every edge of the graph. The minimum vertex cover problem is the optimization problem of finding a smallest vertex cover in a given graph. In short, it is to find a minimum set of vertices to track all edges.

• Input: Set $\mathbf{V}$, Set $\mathbf{E}\subseteq \{\{u,v\}|u,v\in \mathbf{V}\}$
• Output: Set $\mathbf{S}\subseteq \mathbf{V}$
• Constraint: For all $\{u,v\}\in \mathbf{E}$, either $u\in \mathbf{S}$ or $v\in \mathbf{S}$
• Objective Function: Minimize $|\mathbf{S}|$

Suppose $\mathbf{V}=\{1,...,n\}$, we can express the output as a vector $\overrightarrow{x}=(x_1,...,x_n{)}^{⊺}$, where $x_i=1$ if $i\in \mathbf{S}$, otherwise, $x_i=0$

We introduce the Incidence Matrix $\mathbf{A}$ for this problem. Matrix $\mathbf{A}$ has the shape of $|\mathbf{E}|\times |\mathbf{V}|$, each row represents a relationship (edge). In each row, two elements are 1, indicating that these two nodes are linked. Therefore, the above problem can be expressed as follows.

• Input:
  • Matrix $\mathbf{A}$
  • vector $\overrightarrow{b}=(1,...,1{)}^{⊺}$
  • vector $\overrightarrow{c}=(1,...,1{)}^{⊺}$
  • Assumption: At each row of $\mathbf{A}$, two elements are 1, others are 0. All elements of $\overrightarrow{b}$ and $\overrightarrow{c}$ are 1.
• Output: vector $\overrightarrow{x}=(x_1,...,x_n{)}^{⊺}$, where $x_i$ is either 0 or 1.
• Constraint: $\mathbf{A}\overrightarrow{x}\ge \overrightarrow{b}$
• Objective Function: Minimize ${\overrightarrow{c}}^{⊺}\overrightarrow{x}$

Rounding

Fractional Vertex Cover

• Input:
  • Matrix $\mathbf{A}$
  • vector $\overrightarrow{b}=(1,...,1{)}^{⊺}$
  • vector $\overrightarrow{c}=(1,...,1{)}^{⊺}$
  • Assumption: At each row of $\mathbf{A}$, two elements are 1, others are 0. All elements of $\overrightarrow{b}$ and $\overrightarrow{c}$ are 1.
• Output: vector $\overrightarrow{x}=(x_1,...,x_n{)}^{⊺}$, where $x_i\in [0,1]$.
• Constraint: $\mathbf{A}\overrightarrow{x}\ge \overrightarrow{b}$
• Objective Function: Minimize ${\overrightarrow{c}}^{⊺}\overrightarrow{x}$

Algorithm

The algorithm is based the fractional vertex cover problem we just defined.

1. Use linear programming to solve fractional vertex cover, and get output vector $\overrightarrow{x}=(x_1,...,x_n{)}^{⊺}$, where $x_i\in [0,1]$
2. For all $0\le i\le n$, let ${x_i}^{{}^{\prime }}=1$ when $x_i\ge 0.5$, otherwise, ${x_i}^{{}^{\prime }}=0$. Let ${\overrightarrow{x}}^{{}^{\prime }}=({x_1}^{{}^{\prime }},...,{x_n}^{{}^{\prime }}{)}^{⊺}$.
3. Return ${\overrightarrow{x}}^{{}^{\prime }}$ as the answer of the vertex cover problem.

Theorem

1. ${\overrightarrow{x}}^{{}^{\prime }}$ is an answer for the vertex cover problem. It satisfies the constraint.
2. It is a 2-approximation algorithm. For any particular input, $SOL\le 2OPT$.

Proof

Here we prove that the algorithm is a 2-approximation algorithm, i.e., $SOL\le 2OPT$ for any input.

Let $\overrightarrow{x}=(x_1,...,x_n{)}^{⊺}$ be the optimal solution for the fractional vertex cover problem. It is the vector in ${[0,1]}^n$ that minimizes ${\overrightarrow{c}}^{⊺}\overrightarrow{x}$ when $\mathbf{A}\overrightarrow{x}\ge \overrightarrow{b}$. On the other hand, let ${\overrightarrow{x}}^{\ast }$ be the vector in ${\{0,1\}}^n$ that minimizes ${\overrightarrow{c}}^{⊺}\overrightarrow{x}$ when $\mathbf{A}\overrightarrow{x}\ge \overrightarrow{b}$. Both of the vectors minimize the objective function with the same constraint, but $\overrightarrow{x}$ is selected from a larger set. $\overrightarrow{x}$ has more chances to minimize the objective function, so the objective value of $\overrightarrow{x}$ is better (thus smaller) than that of ${\overrightarrow{x}}^{\ast }$, i.e., ${\overrightarrow{c}}^{⊺}\overrightarrow{x}\le {\overrightarrow{c}}^{⊺}{\overrightarrow{x}}^{\ast }$.

Now, consider the value of ${x_i}^{{}^{\prime }}$. By the rounding at the step 2 of the algorithm, we have ${x_i}^{{}^{\prime }}\le 2x_i$. Then

$$SOL={\overrightarrow{c}}^{⊺}{\overrightarrow{x}}^{{}^{\prime }}=\sum _i{x_i}^{{}^{\prime }}\le 2\sum _i{x}_i=2{\overrightarrow{c}}^{⊺}\overrightarrow{x}\le 2{\overrightarrow{c}}^{⊺}{\overrightarrow{x}}^{\ast }=2OPT$$