Question

3. Vertex Cover on Planar Graphs. The problem Planar Vertex Cover is to find a smallest set C of vertices in a given planar graph G such that every edge in G has at least one endpoint in C. It is known that Planar Vertex Cover is NP-hard. Develop a polynomial time approximation scheme (PTAS) for the problem.

Answer 1

Algorithm : Approx-Vertex-Cover(G)
1. C←∅
2. while E ≠ ∅
       pick any {u, v} ∈ E
       C ← C ∪ {u, v}
       delete all edges incident to either u or v
return C

As it turns out, this is the best approximation algorithm known for vertex cover. It is an open problem to either do better or prove that this is a lower bound.

Observation: The set of edges picked by this algorithm is a matching, no 2 edges touch each other (edges disjoint). In fact, it is a maximal matching. We can then have the following alternative description of the algorithm as follows.

Find a maximal matching M
Return the set of end-points of all edges ∈ M .

Analysis :
the algorithm only terminates when all edges are covered
Solution value:
• Let (u 1 , v 1 ), (u 2 , v 2 ), ..., (u k , v k ) be edges picked in step 2 of the algorithm
• |V C| = 2k

Claim:
OPT ≥ k
• The edges (u 1 , v 1 ), (u 2 , v 2 ), ..., (u k , v k ) are disjoint.
• For each edge (u i , v i ) , any vertex cover must contain u i or v i .

Conclusion: k ≤ OPT ≤ |V C| ≤ 2k
In other words: OPT ≤ |V C| ≤ 2OPT .
We have a 2-approximation algorithm.