We will implement a log(n)-approximation algorithm, a 2-approximation algorithm for this problem (this differs from the 2-approximation in class), and an exact (but slow) algorithm. log(n)-Approximation Algorithm
SmartGreedyVertexCover(G)
Input: A graph G.
Output: A set of vertices that form a (not necessarily optimal) vertex cover.
1: C ←∅
2: while G has at least one edge do
3: v ← vertex in G with maximum degree
4: G ← G \ v (This also removes all edges adjacent to v)
5: C ← C ∪ v
6: return C
Implement this algorithm.
2-Approximation Algorithm BasicGreedyVertexCover(G)
Input: A graph G.
Output: A set of vertices that form a (not necessarily optimal) vertex cover.
1: C ←∅
2: while G has at least one edge do
3: (u,v) ← any edge in G
4: G ← G \{u,v} (This also removes all edges adjacent to u and v)
5: C ← C ∪{u,v}
6: return C
Implement this algorithm.
Exact Algorithm
Implement a brute force (exact) algorithm for vertex cover.
Format:
The input graph will be undirected and simple (no self loops or multiple edges). The format will be a simple edge list. There will be n vertices and m edges. Each edge in the graph will be represented by a pair of vertex identifiers. Note that I will not give you graphs with isolated vertices. All edge lists will begin at 0.
For example the following graph is represented by the list:
1 2
1 3 2 3 1 4 0 5 4 3 3 0
