HW#5 --- last modified May 11 2022 22:13:04.

Solution set.

Due date: May 16

Files to be submitted:
  Hw5.zip

Purpose: To gain experience with NP-completeness proofs and approximation algorithms.

Related Course Outcomes:

CLO5 -- Given a problem determine within NP that is promised to be either in P or NP-complete prove which it is

CLO7 -- 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.

1. Consider the language `VERTEX-COVER_k = {langle G rangle | G mbox( encodes a graph with a vertex cover of size ) k }`. Prove for any fixed `k > 1` that `VERTEX-COVER_k` is in `P`.
2. Give a family of graphs `G_3, G_4, G_5 ... G_n` where the subscript denote the number of vertices in the graph on which vertex cover is at least `4/3` the optimal cover.
3. Let `L = {langle s_1, ..., s_n, k rangle | s_i mbox(are binary strings, ) k>0 mbox(, and ) k mbox( is the length of the shortest string that has all ) s_i \mbox('s as a substring) }.` Prove `L` is in NPC.

For the coding part of the homework, I want you to write program ApproxTSP in either Java or Python. It will be run from the command line with a syntax:

java ApproxTSP some_file_name.txt

or

python ApproxTSP.py some_file_name.txt

Here some_file_name.txt should be the name of a file containing an weighted adjacency matrix for the distances between cities. I.e., each line in any file your program will be tested on will consist of one row of such an adjacency matrix where the entries are nonnegative integers and integers are separated by spaces. The `i`th line's `j`th column represents the distance between cities `i` and `j`. Tests inputs will always be symmetric matrices. That is, `m_{ij} = m_{ji}`. Below is an example of what the contents of some_file_name.txt might look like:

0 4 5 3
4 0 3 5
5 3 0 4
3 5 4 0

On such an input your program should output the tour that the APPROX-TSP-TOUR algorithm from class would compute. For example,

1 2 3 4

for the graph above. To do this you should implement this algorithm from class.

Point Breakdown