Approximation-Algorithms Programming Assignment 8–Solution

Description

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 n 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 n fu; vg (This also removes all edges adjacent to u and v)

5. C C [ fu; vg

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:

0	1	1 2
		1 3
5		2 3
		2
		1 4
4	3	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.

Additionally:

• There will be two test runs, one at 10am and one at 8pm on Wednesday, 12/04. A feedback containing only what your program scores (on the same test cases that will be used to grade it). I may be able to give you an idea of what your program is failing on (if you have made an effort to test it), so please take advantage of these runs.

• Late submissions are not accepted for this assignment.

2 of 2