NP Complete Project Problem Specification

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

Problem | Prefix Traveling Salesperson | tsp_ Longest Path | fp_

ALl problems with have the following: Program Type | Suffix brute force | bf back tracking | bt back tracking with ordering | bt_ordering random approximation | random greedy approximation | greedy

Weighted Undirected Graph - TSP

The input is a weighted graph specified by a line containing the number of vertices n and the number of edges m. This is followed by m lines containing the edges given in u v w format, representing an edge between u and v of weight w (and w is an integer). TSP graphs are undirected and edges will be listed only once and the graph will be 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
b c 4
a c 5

Example TSP output:

12
a b c a

Weighted Directed Graph - Longest Path

The input is a list of edges. LP graphs are directed and are not necessarily complete graph. 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}.