Approximation Algorithm - Part 2 ( Vertext Cover)

Vertex Cover

§Instance:  An undirected graph G = (V , E ).

§Feasible Solution: A subset C ⊆ V such that at least one vertex of every edge of G belongs C.

§Value: The value of the solution is the size of the cover, |C |, and the goal is to minimize it.

§NP-Complete Problem

Goal

§Finding a minimum vertex cover in a graph. Such that every edge has at least one end vertex in the set. 

§ In general can be very difficult to find. But it is not too hard to find a vertex-cover that is near optimal.

 

Approximate Algorithm for Vertex Cover

Approx-Vertex-Cover (G = (V, E))  

{       

    C = empty-set;  

    E'= E;  

    While E' is not empty do  

      {  

    Let (u, v) be any edge in E’

    Add u and v to C;  

    Remove from E' all edges incident to   u or v  

      }  

    Return C  

}  

The idea is to take an edge (u, v) one by one, put both vertices to C, and remove all the edges incident to u or v. We carry on until all edges have been removed. C is a VC. 

Example

Step-1

The edge (b,c), shown heavy, is the first edge chosen by APPROX-VERTEX-COVER. Vertices b and c, shown lightly shaded, are added to the set C containing the vertex cover being created. Edges (a, b), (c, e), and (c,d), shown dashed, are removed since they are now covered by some vertex in C. 

Step-2

Step-3

 Edge (e, f) is added to A.  Edge (d,g) is added to C. 

Step-4

The set C, which is the vertex cover produced by APPROX-VERTEX-COVER, contains the

 six vertices b, c, d, e, f, g. Approximate vertex cover. C=6

Optimal Vertex Cover 

Running Time

    The running time of this algorithm is O(V+E), using the adjacency list to represent E`. The algorithm has O(|E|) iterations of the loop, across all loop iterations, O(|V|) vertices are added to C. Therefore it is O(E + V), so is polynomial.      

Approx-Vertex-Cover (G = (V, E))  

{       

    C = empty-set;  

    E'= E;  

    While E' is not empty do  -----------------  > O (E)

      {  

    Let (u, v) be any edge in E’

    Add u and v to C;  -------------------- ----->  O (V)

    Remove from E' all edges incident to   u or v 

      }  

    Return C

}  

  O ( E + V )

§Theorem: APPROX-VERTEX-COVER is a polynomial-time 2-approximate algorithm i.e., the algorithm has a ration bound of 2.
§Goal: Since this a minimization problem, we are interested in the smallest possible C/C*. Specifically we want to show C/C* ≤ 2 = p(n).

In other words, we want to show that APPROX-VERTEX-COVER algorithm returns a vertex-cover that is at most twice the size of an optimal cover.

§Proof: Let the set C and C* be the sets output by APPROX-VERTEX-COVER and OPTIMAL-VERTEX-COVER respectively.

§Let, A = set of edges picked by an approximation algorithm. [the set of edges selected by line 4]

§No 2 edges in A share an endpoint

§Formally, since no two edges in A are covered by the same vertex from c*.

§No two edges in a share a vertex.

§For any two edges one of them must be selected first (line 4), and all edges sharing vertices with the selected edge are deleted from E′ inline 6.

§So are no longer candidates on the next iteration of line 4. The lower bound:

| C* | ≥ A        ----------------------------- (1)

§The lower bound:

             | C* | ≥ A       

§In line 4, we pick an edge for which neither of its endpoints are already in C,

§So, Upper bound:

            |C| = 2|A|------------------------- (2)

Therefore:   |C| = 2|A| <= 2|C*|

|c|/|c*| ≤ 2 = p(n)

§That is, |C| cannot be larger than twice the optimal, so it is a 2-approximation algorithm for Vertex Cover.

[Because we have added both vertices, we get c = 2|A| but OPTIMAL-VERTEX-COVER would have added one of two.  c/c* ≤ p(n) = 2.]