Question

GVC_E(V,E)

1. C =Φ

2. while ( E≠ Φ)

3. do

4. { select an edge (u,v)∈E;

5. C = C∪{u}∪{v};

6. delete u and v from V and edges with u or v as an endpoint from E;

7. }

8. for each u∈C

9. { if C\{u} is a valid cover;

10. C = C\{u};

11. }

How can I complete the pseudo code on line 4 and line 8 by adding a heuristic specifying how to select a node

Answer 1

Here in both line 4 and 8, there is no such heuristic. You can select any arbitrary edge in line 4 among all the remaining edges available on your graph, to add its vertices for vertex cover. And similarly you can select any vertex u in line 8 to check whether its removal will still let set C to be a vertex cover.

However this is Greedy algorithm, we can select edge e = (u,v) in line 4 such that vertex u and vertex v has maximum possible degree.

Consider 2 graphs shown below:-

Here in the left side graph, if we remove edge (u,v) where sum of degree of vertices u and v is maximum and add vertex u and v i.e. {u,v} as greedy choice of edge-cover then this strategy is giving optimal result.

But in the right side graph, if we remove edge (u,v) as per the Greedy choice, then we will be left with 6 vertices and 3 edges (u₁,v₁), (u₂, v₂) and (u₃,v₃) and this Greedy algorithm will select all the vertices in each of these edges as the edge cover and hence the edge cover will be {u,v, u₁,v₁, u₂, v₂ u₃,v₃ } which is the worst choice while the optimal choice is {u, u₁ , u₂, u₃} .

This example shows that Greedy strategy will not give optimal result.