Deliverables:
GitHub Classroom: https://classroom.github.com/a/Gbga1MOi
Required Files: compile.sh, run.sh
Optional Files: *.py, *.java, *.clj, *.kt, *.js, *.sh
By now you are very familiar with the Vertex Cover problem:
Input: A graph G = (V,E).
Goal: Find a vertex cover of minimum size.
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.
1 of 2
CPE 349 – Algorithms Approximation Algorithms – Programming Assignment 8
Fall 2019 Due: Thursday, December 5th
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
What to turn in via GitHub Classroom by 8pm of the due date:
- Accept the following GitHub Classroom assignment: https://classroom.github.com/a/Gbga1MOi. This will create a GitHub repository which you will use to submit your source code for this assignment. The repository will also include some basic sample inputs and outputs.
- Your algorithm should take an edge list and output the vertices corresponding to three vertex covers.
- Your program must read input from a file (given as the first command line argument) and write output to stdout.
