NP Complete Project Problem Specification

This document outlines the input and output specifications for each NP-complete problem. For each problem, sample input and output are provided.

Weighted Graph Problems (TSP, Longest Path)

For traveling sales person, the names of the two programs are:

• cs412_tsp_exact.py
• cs412_tsp_approx.py

For the longest path problem, the names of the two programs are:

• cs412_longestpath_exact.py
• cs412_longestpath_approx.py

The input is a weighted graph specified by a line containing the number of vertices n and the number of edges m followed by m lines containing the edges given in u v w format, representing an edge between u and v of weight w. TSP graphs are undirected and edges will be listed only once and the graph will be a complete graph. LP graphs are undirected and edges will be listed once (but it is not necessarily a complete graph).

The output contains two lines: the length of the path on one line (as an integer) followed by a list of vertices for the path/cycle on the second line.

Example TSP input:

3 3
a b 3.0
b c 4.2
a c 5.4

Example TSP output (you can round the answer to the nearest .0000)

12.6000
a b c a

Example LP input:

3 3
a b 3
b c 4
a c 5

Example LP output:

9
a c b

Max Clique, Vertex Cover, Min Graph Coloring

For max clique, the program file names are:

• cs412_maxclique_exact.py
• cs412_maxclique_approx.py

For min graph coloring, the program file names are:

• cs412_mingraphcoloring_exact.py
• cs412_mingraphcoloring_approx.py

For the minimum vertex cover problem, the program file names are:

• cs412_minvertexcover_exact.py
• cs412_minvertexcover_approx.py

For Max Clique and Vertex Cover, your input is an undirected graph. The first line will list the number of edges m. The remaining m lines are a list of vertice pairs

• u v* where an edge exists between u and v. The vertices are inferred from the edge list.

Sample Max Clique and Vertex Cover input:

2
a b
b c

This is a graph with three vertices, a, b, and c and two edges {a, b} and {b, c}.

For max clique and vertex cover, the output should be the structure (clique or vertex cover) specified by the vertices on a single line, space separated.

Sample Max Clique output:

a b

Sample min Vertex Cover output:

b

For min color, you should specify the number of colors on the first line, followed by the vertex color assignments in the format vertex name color. Your “color name” data should just be integers 0 through k-1 (where k is the min number of colors).

Sample Min Color Output

2
a 0
b 1
c 0

Max 3SAT

The program file names for max 3SAT are:

• cs412_max3sat_exact.py
• cs412_max3sat_approx.py

The first line of input specifies n the number of variables and m the number of clauses. The n variables are numbered 1 through n. The clauses are encoded as three indices with a minus sign (-) denoting negation (this is why they are numbered from 1 to n, since -0 is trouble).

So the clause \( (x_1 \lor \overline{x_2} \lor x_3) \land (\overline{x_1} \lor x_2 \lor \overline{x_3})\)

Would be encoded as:

3 2
1 -2 3
-1 2 -3

The first line of the output is the number of clauses satisfied. This is followed by n lines where each line details the variable’s assignment of true or false and is written as the variable number followed by a T or F.

Sample Output:

2
1 T
2 T
3 F

This output corresponds to the claim that if we set \(x_1\) to true, \(x_2\) to true, and \(x_3\) to false, we satisfy two clauses.

Min Set Cover

The program file names are:

• cs412_minsetcover_exact.py
• cs412_minsetcover_approx.py

The first line of the input will be the number of elements n followed by the number of subsets m. Your universe / elements are the numbers \(1, \ldots, n\) (count from 1). The next m lines will be each subset.

Sample Input

5 3
1 2 3
2 4
3 4 5

The input above is for the instance of the problem U={1, 2, 3, 4, 5}, S={{1, 2, 3}, {2, 4}, {3, 4, 5}}.

The output should be the indices of the subsets (indexed from 0) that are used to cover the universe (with a minimum number of subsets):

Sample Output

0 2

Meaning that the smallest cover is {1, 2, 3}, {3, 4, 5}.