HW#5 --- last modified February 06 2019 04:20:47..
Solution set.
Due date: May 11
Files to be submitted:
Project.zip
Purpose: To gain experience with NP-completeness proofs and approximation
algorithms.
Related Course Outcomes:
The main course outcomes covered by this assignment are:
LO6 -- Given a problem determine within NP that is promised to be either in P or NP-complete prove which
LO7 -- Analyze or code an approximation algorithm for a optimization problem whose decision problem is NP-complete.
Specification:
This homeworks consists of the following written problems, together with a programming exercise described below.
Submit the written problems in Hw5.pdf as part of your Hw5.zip file. Submit your code in this ZIP file as well.
- Show the problem of whether the maximum independent set of a graph `G` has size `k` is `NP`-hard.
- A `k`-coloring of a graph is `G=(V,E)` is a map from `f: V -> {1, ..., k}` such that if `(i,j) in G`
then `f(i) ne f(j)`. Show that the language consisting of encodings of graphs which are 2-colorable is in `P`.
- Prove that the language consistent of pairs `(langle G rangle, k)` where `G` is a graph and `k` is
a positive integer such that `G` is `k` colorable is `NP`-complete.
For the coding part of the assignment I would like you to code the approximate vertex cover algorithm
discussed in class and submit this in a file ApproxVertexCover.java as part of your HW5.zip file. This
program will be compiled from the command line with the syntax:
javac ApproxVertexCover.java
It will then be run with a line like:
java ApproxVertexCover some_file_with_graph.txt
Here some_file_with_graph.txt will be a file containing the adjacency matrix for a graph. For example,
0 1 0 0 0 0 0
1 0 1 0 0 0 0
0 1 0 1 1 0 0
0 0 1 0 1 1 1
0 0 1 1 0 1 0
0 0 0 1 1 0 0
0 0 0 1 0 0 0
which corresponds to the graph of Figure 35.1 in the book. On such an input, your program should run
the approximate vertex cover algorithm we has and output the vertices in the cover it finds. The edge
it should pick in the line pick an arbitrary edge should be chosen uniformly at random from the edgeset
`E'`. It should print out the edges chosen. One possible output of the algorithm on the above graph is:
Edges Chosen:
(1,2)
(4,5)
(3,6)
Cover Found:
1 2 3 4 5 6
I would like you to test your program on a variety of graph for which you hand calculate the optimal
vertex cover and see how this algorithm does versus the optimal. Write up your results in experiments.txt.
Point Breakdown
Written problems (2pts each, 0 wrong, wrong-track, 1 partially correct, but exposition issues,
2 fully correct) |
6pts
|
Java Coding Guidelines (0.5pts), file reads input correctly (0.5pts) |
1pt
|
Edges selected uniformly at random as per description above |
1pt
|
Implementation of approximation algorithm works on test cases |
1pt
|
Your experiment write-up in experiments.txt |
1pt
|
|