Description

In this assignment you will implement approximation algorithm for the Minimum Vertex Cover problem. The tasks are described as follows:
1. Implement the 2-approximation algorithm (as described in the textbook by Cormen et al.) of the Minimum Vertex Cover problem.
2. In the approximation algorithm, you need to repeatedly choose an edge until you find a vertex cover. In this assignment you will implement two schemes of choosing edge in each step as follows.
a. Pick edge randomly.
b. Pick the edge (u,v) for which the sum of the uncovered edges of the graph incident to u and v is maximum. You can also think this as picking the edge (u,v) for which deg(u) + deg(v) is maximum where deg(u) is the degree of u in the current graph (Note that in each step you are removing some edges of the original graph).
4. Construct a graph for which the 2-approximation algorithm will perform worst (no matter how you pick the edges!). Submit the test case of this graph in a txt file along with your source code and report.