Question

Consider a tree with 13 nodes: the root has 4 children and each of these children has 2 children. Consider the following greedy algorithm for vertex cover: add the node with the highest degree to the vertex cover, remove all edges incident to this node, and repeat until there are no edges left. What approximation ratio is achieved by the algorithm on this graph? Give your answer to 2 decimal places.

Can someone help me with this question? Thanks.

Answer 1

Vertex cover: Subset of its vertices such that for every edge (u, v) of the graph, either ‘u’ or ‘v’ is in vertex cover.

Degree: Degree of node in a tree is the number of children it has. In binary tree degree can be 0(leaf nodes),1 or 2.

Using the greedy algorithm we first add the vertex with highest degree and remove all the edges in the tree which are incident on to this vertex, repeat the process until the tree has no edges.

Using the general algorithm we get the complexity O(V+E), but using approximation this can be reduced to polynomial time.

Using the PCP technique the best approximation ratio that can be achieved is 1.12.