Projects

1 - Escape from Exponential Island

Overview

Many important computational problems have search spaces that grow too quickly for exhaustive search to remain practical. In this project, your group will investigate one known NP-complete problem by approaching it from several directions. You will begin by defining the decision and optimization versions of the problem, explaining why the decision version is NP-complete, and then studying several approaches to the optimization version.

Your group will implement a straightforward exact algorithm, improve the exact search using pruning or related techniques, and design approximation methods or heuristics that can produce useful feasible solutions for instances that are too large to solve exactly.

This project is not only about writing code. You will analyze running time, measure how the input space grows, evaluate the quality of feasible solutions, compare your results against benchmark instances, and present your findings to the class.

The goal is to understand how computational hardness appears in practice. You should come away from this project with a better sense of why brute force fails, why pruning can help but does not remove worst-case hardness, why approximation methods and heuristics are often necessary for large instances, and why problem-specific structure or stronger exact methods can sometimes change what is computationally feasible.

Learning Objectives

By completing this project, you will be able to:

• Define the decision and optimization versions of a known NP-complete problem.
• Explain why the decision version of the problem is in NP.
• Describe a reduction that establishes NP-completeness.
• Implement an exact algorithm for a known NP-complete optimization problem.
• Measure how quickly the search space grows as the input size increases.
• Improve exact search using pruning, backtracking, branch-and-bound, or related techniques.
• Design and evaluate approximation methods or heuristics that use repeated trials, randomized choices, or other stochastic techniques to explore multiple regions of the solution space.
• Use exact optima, lower bounds, or upper bounds to evaluate the quality of feasible solutions.
• Explain how special input structure or stronger exact methods can change what is computationally feasible.
• Present algorithmic ideas clearly and critique other groups’ approaches.

Exact Algorithms, Improved Exact Algorithms, and Heuristics

In this project, an exact algorithm is an algorithm that is guaranteed to return an optimal solution when it terminates. A brute-force search is exact because it considers every possible solution, but it quickly becomes impractical as the input size grows.

An improved exact algorithm is still guaranteed to return an optimal solution, but it tries to avoid unnecessary work. Techniques such as pruning, backtracking, branch-and-bound, and short-circuiting can often reduce the amount of search dramatically. These techniques improve practical performance, but they do not remove the worst-case difficulty of the problem.

An approximation method or heuristic is different. It is designed for instances where exact search is too expensive. It returns a feasible solution that may not be optimal, and the goal is to evaluate how good that solution is. In this project, your approximation methods or heuristics should use repeated trials, randomized choices, or other stochastic techniques so that you can study a range of possible solution values rather than reporting a single result.

Some approximation methods come with formal performance guarantees. Other heuristics may work well in practice but do not guarantee a fixed distance from the optimum. In either case, your group must explain how solution quality will be evaluated.

Project Problems

Each group will work on one of the following problems:

• Traveling Salesperson Problem
• Minimum Graph Coloring
• 3-SAT / Max-SAT
• Minimum Vertex Cover
• Longest Path
• Maximum Clique

Your group’s exact requirements will depend slightly on the problem you choose, but every group will follow the same general project template: theory and reductions, exact search, improved exact search, approximation or heuristic search, empirical evaluation, and presentation.

For this project, the Longest Path problem should be treated as the unweighted, undirected version: given an undirected, unweighted graph, find a simple path containing as many edges as possible. In this setting, every simple path has length at most (n-1), where (n) is the number of vertices. This gives a simple upper bound for evaluating heuristic solutions. The decision version asks whether the graph contains a simple path with at least (k) edges, and the special case (k=n-1) corresponds to Hamiltonian Path.

Project Template and Group Responsibilities

Each group will study one NP-complete optimization problem using a common project template. The details will vary by problem, but every group will investigate the same major questions:

• What are the decision and optimization versions of your problem, and why is the decision version NP-complete?
• What does a straightforward exact solution look like?
• How quickly does the search space grow?
• How can the exact search be improved without giving up optimality?
• What approximation methods or heuristics work when exact search becomes infeasible?
• How can the quality of feasible solutions be evaluated?
• What problem-specific structure allows closely related problems to be solved efficiently, or enables stronger pruning during exact computation?
• What can reductions to or from related NP-complete problems reveal about algorithm design and solution quality?

This template is intended to help you compare different approaches to the same problem. You should not think of the project as several disconnected tasks. Instead, each part should help explain the same central issue: how computational hardness affects algorithm design in practice.

Group Roles

Each group should assign four primary roles. These roles are intended to make responsibilities clear, but all group members are expected to understand the complete project.

Theory and Reduction Lead

• Defines the optimization and decision versions of the problem.
• Explains why the decision version is in NP.
• Presents the NP-completeness reduction.
• Coordinates the reduction experiment or related-problem comparison.
• Explains what the reduction does and does not preserve.

Baseline Exact Search and Bound Computation Lead

• Implements the brute-force exact solver.
• Computes and explains the size of the search space.
• Designs the small-instance experiments where exact optima can be computed.
• Produces baseline timing data and plots showing where brute force becomes infeasible.
• Computes exact optimal values for small test cases so the group can evaluate solution quality.
• Implements simple lower or upper bound computations for larger test cases when exact optima are unavailable.
• Helps define the result format used to compare exact, improved exact, and non-exact solution methods.

Improved Exact Search and Pruning Lead

• Implements pruning, backtracking, branch-and-bound, or another exact-search improvement.
• Explains why the improved method still guarantees an optimal solution.
• Uses bounds to prune parts of the search space when appropriate.
• Reports how much search was avoided, such as recursive calls, states expanded, states pruned, or candidate solutions discarded.
• For TSP or Maximum Clique, this role may involve stronger branch-and-bound methods.

Heuristic Search and Benchmark Lead

• Designs and implements approximation methods or heuristics.
• Incorporates repeated trials, randomized choices, random restarts, local search, simulated annealing, genetic algorithms, or another approved stochastic strategy.
• Evaluates solution quality across multiple runs, including best, worst, mean, and median results.
• Runs benchmark experiments and interprets leaderboard performance.
• Coordinates with the Baseline Exact Search and Bound Computation Lead to compare feasible solutions against exact optima or valid bounds.

Groups may divide the work differently with instructor approval, but every group member must have a clearly identified role. Each member is expected to understand the group’s overall approach well enough to explain how their component connects to the rest of the project.

Individual Accountability

The project will be graded as both a group submission and an individual contribution. The group grade will reflect the quality of the final code, analysis, presentation, and results. The individual portion will reflect each member’s documented contribution, checkpoint submissions, presentation role, and peer/self evaluations.

If a group member is not contributing adequately, the rest of the group should communicate with the instructor before the final deadline. The checkpoint structure is intended to make progress visible throughout the project rather than only at the end.

Project Components

Your group will complete several connected project components. These components are not intended to be completed strictly one after another. Different group members should begin working on different components early in the project, while coordinating shared definitions, input formats, test cases, and experimental results.

For example, the Theory and Reduction Lead can begin formalizing the decision and optimization versions while the Baseline Exact Search and Bound Computation Lead starts building small test cases. The Heuristic Search and Benchmark Lead can begin studying possible heuristic strategies before the improved exact solver is finished. The components depend on one another, but the work should proceed in parallel.

The checkpoints provide deadlines for visible progress, but they should not be interpreted as permission to delay a role until late in the project.

Component 1: Problem Definition and NP-Completeness

Your group must define your problem precisely.

You should identify:

• The optimization version of the problem.
• The decision version of the problem.
• The certificate for the decision version.
• Why the certificate can be checked in polynomial time.
• A reduction showing that the decision version is NP-hard.
• Why these facts imply that the decision version is NP-complete.

You should also explain how the optimization version relates to the decision version. For example, if you had an efficient algorithm for the optimization version, how could you use it to answer the decision version?

This component establishes the theoretical foundation for the project and should begin early.

Component 2: Brute-Force Exact Solver

Your group must implement a straightforward exact solver for your problem. This version should prioritize correctness over efficiency. It is acceptable, and expected, that this method will only work for small inputs.

Your analysis should answer questions such as:

• What is the size of the search space as a function of the input size?
• What is the worst-case asymptotic running time?
• How large can the input become before brute force is no longer practical?
• How does the empirical running time compare to your analytical prediction?
• Which small test cases can be solved exactly and used as ground truth later?

This component establishes the baseline against which later methods will be compared.

Component 3: Bounds and Baseline Evaluation

Your group should compute exact optima on small instances and identify useful lower or upper bounds for larger instances.

The purpose of this component is to make later solution-quality results meaningful. If your method returns a feasible solution on a large instance, you need some way to evaluate whether that solution is good.

Depending on your problem, possible bounds include:

• TSP: MST lower bound, 1-tree lower bound, nearest-neighbor or greedy tour upper bound.
• Minimum Vertex Cover: maximal matching lower bound, greedy vertex cover upper bound, exact optimum for small graphs.
• Minimum Graph Coloring: clique-size lower bound, greedy coloring upper bound, exact optimum for small graphs.
• Maximum Clique: greedy coloring upper bound, exact optimum for small graphs.
• Longest Path: (n-1) upper bound for unweighted graphs, exact optimum for small graphs, tree diameter for tree instances.
• 3-SAT / Max-SAT: number of clauses as an upper bound, randomized assignment baseline, exact optimum for small formulas.

Your group should explain whether each bound is a lower bound or an upper bound, whether it applies to minimization or maximization, and how it can be used to evaluate solution quality.

Component 4: Improved Exact Search

Your group must improve the exact solver while still guaranteeing an optimal answer. Possible techniques include pruning, backtracking, short-circuiting, branch-and-bound, or problem-specific observations that safely eliminate parts of the search space.

Your improved exact solver must still be exact. It is not enough for the method to usually find good answers; when it terminates, it must return an optimal solution and be able to justify that no better solution exists.

Your analysis should compare this version against the brute-force version. You should report not only running time, but also evidence of how much search was avoided. For example, you might report the number of recursive calls, branches explored, branches pruned, candidate solutions considered, or partial solutions discarded.

Maximum Clique Note

Maximum Clique has a slightly different flavor from some of the other project problems. It has a clean relationship to Independent Set through graph complementation, and it supports elegant exact-search improvements using recursive backtracking and branch-and-bound.

A useful way to think about the recursive search is that you are building a clique one vertex at a time. The first choice is which vertex belongs in the clique. Since you do not know which choice leads to a maximum clique, you try all possible choices. Once you choose a vertex, the problem becomes smaller: every future vertex must be adjacent to that chosen vertex and to every other vertex already in the clique.

In a recursive implementation, you may maintain:

• C: the clique currently being built.
• P: the set of vertices that can still be added to C.

The important invariant is that every vertex in P is adjacent to every vertex in C. Initially, C is empty and P contains all vertices. This is valid because the empty clique imposes no adjacency restrictions.

When you choose a vertex v from P, the recursive call uses:

C' = C ∪ {v}
P' = (P - {v}) ∩ neighbors(v)

Here, neighbors(v) is the set of vertices adjacent to v. Intersecting with neighbors(v) ensures that future choices remain adjacent to the newly chosen vertex.

Maximum Clique also supports useful pruning bounds. For example, if the current clique has size |C| and there are only |P| candidate vertices left, then this branch can produce a clique of size at most:

|C| + |P|

If this value is no better than the best clique already found, the branch can be pruned.

A stronger upper bound can be obtained by greedily coloring the subgraph induced by P. A clique can contain at most one vertex from each color class. Therefore, if the remaining candidate graph can be colored using k colors, then no clique inside P has size larger than k. This gives the upper bound:

|C| + k

Groups working on Maximum Clique should emphasize the contrast between brute force, recursive backtracking, branch-and-bound, and heuristic exploration. Maximum Clique does not have the same kind of straightforward approximation story as problems such as Vertex Cover or TSP, so the non-exact component should focus on randomized or repeated heuristic methods and should report the distribution of clique sizes found across multiple runs.

TSP Improved Exact Search Note

TSP groups should consider implementing branch-and-bound as their improved exact search method. TSP is a historically important example where exact algorithms can solve instances far beyond naive brute force by using lower bounds to prune the search space.

A TSP branch-and-bound solver should:

• Maintain an incumbent tour, which is the best complete tour found so far.
• Explore partial tours recursively or with a priority queue.
• Compute a valid lower bound on the cost of completing each partial tour.
• Prune any partial solution whose lower bound is no better than the incumbent.
• Return an optimal tour when the search completes.
• Report evidence that the algorithm certified optimality, not merely that it found a good tour.

Your lower bound should be stronger than simply using the cost of the current partial path. Possible choices include an MST-based completion bound, a 1-tree lower bound, or another approved bound.

Your analysis should compare brute force and branch-and-bound on the same families of instances. Report the number of states expanded, the number of states pruned, the best tour found early in the search, and the largest instances for which your solver can certify optimality. You should also explain why your lower bound is valid and why the algorithm remains exact.

The goal is not to claim that TSP becomes easy. The goal is to show that there is a large practical gap between naive exhaustive search and more sophisticated exact optimization.

Component 5: Approximation Methods and Heuristics

For larger instances, exact algorithms may be too expensive even after pruning. In this component, your group will design one or more methods that produce useful feasible solutions without necessarily guaranteeing optimality.

Your approximation method or heuristic must include some mechanism for exploring multiple regions of the solution space. For example, your method might use randomized starting points, randomized choices during construction, repeated trials, local search with random restarts, simulated annealing, genetic algorithms, or another approved stochastic strategy. The goal is to avoid reporting only a single local minimum or maximum and instead study the range and quality of solutions your method can produce.

Your method should be evaluated by both speed and solution quality. You should compare feasible solutions to exact solutions on small instances where the optimum is known. For larger instances, you should compare your results to lower or upper bounds on the optimum when possible.

Your analysis should address questions such as:

• How quickly does your method produce an initial feasible solution?
• How does solution quality vary across repeated runs?
• What are the best, worst, mean, and median solution values over multiple trials?
• Does the solution improve if the method is given more time or more trials?
• How close is your solution to the optimum on instances where the optimum is known?
• What lower or upper bounds can you use when the optimum is not known?
• What tradeoffs did your group make between running time, solution quality, and randomness?

Component 6: Structure, Tractability, or Advanced Exact Search

NP-complete problems are hard in general, but that does not mean every instance is equally difficult. Additional structure can sometimes make a closely related problem polynomial-time solvable. In other cases, stronger exact methods can solve much larger instances than naive brute force, even though the worst-case running time remains exponential.

For this component, your group will complete one of the following tasks, depending on your problem.

Polynomial-Time Special Cases

For most problems, your group will study a restricted version of the problem that has a polynomial-time algorithm. Your group should:

• Clearly define the restricted input class.
• Explain why the restriction changes the computational difficulty of the problem.
• Describe a polynomial-time algorithm for the restricted case.
• Implement the algorithm or demonstrate it carefully on representative examples.
• Compare the restricted-case algorithm to your brute-force, improved exact, and non-exact approaches.
• Discuss what this special case reveals about the difference between worst-case hardness and practical algorithm design.

Possible special cases include:

• 3-SAT: 2-SAT
• Minimum Vertex Cover: bipartite graphs
• Minimum Graph Coloring: bipartite graphs or chordal graphs
• Longest Path: trees
• Maximum Clique: interval graphs or chordal graphs

Advanced Exact Search Alternative

Some groups may satisfy this component by extending their improved exact search instead of studying a polynomial-time special case. This option is especially appropriate for TSP and Maximum Clique, where strong branch-and-bound methods can illustrate the gap between naive exhaustive search and more sophisticated exact optimization.

Groups choosing this option should explain:

• What additional pruning or bounding method was used.
• Why the method remains exact.
• How the method changes the size of instances that can be solved optimally.
• What kinds of instances are still difficult.
• How this advanced exact method compares to the group’s approximation methods or heuristics.

Component 7: Reduction Experiment

As an additional comparison, each group will examine at least one reduction involving its problem. In some cases, this may be the reduction used to show that the decision version of the problem is NP-complete. In other cases, the group may explore a reduction to or from another problem studied by a different group.

When possible, groups may run another group’s method on the reduced instance and compare the result to their own approach. For example, a reduction might transform an instance of one NP-complete problem into an instance of another problem, allowing a different group’s solver, approximation method, or heuristic to be applied.

This experiment should be interpreted carefully. A reduction that preserves yes/no answers for decision problems does not necessarily preserve solution quality for optimization problems. Therefore, the goal is not simply to find a better method by converting the problem. The goal is to understand what reductions do and do not preserve, and to investigate whether ideas from one problem can provide useful insight into another.

Your analysis should address questions such as:

• What reduction did your group study?
• What is preserved by the reduction?
• Does the reduction preserve solution quality in a way that is useful for approximation?
• Were you able to run another group’s method on the reduced instance?
• If so, how did the result compare to your own approach?
• What does this experiment reveal about the relationship between the two problems?

Benchmark Evaluation

Your approximation methods or heuristics will be evaluated on benchmark instances using the autograder. These benchmarks are designed to reward robust strategies rather than solutions tuned to a single input.

A leaderboard will allow groups to compare performance across the benchmark set. The purpose of the leaderboard is not merely to win; it is to motivate careful design, empirical measurement, and thoughtful tradeoff analysis.

Your final report and presentation should explain the strategy behind your method, not just its leaderboard score.

Presentations and Peer Critique

At the end of the project, each group will present its approach and results to the class. Each group member must present a meaningful part of the project.

Your presentation should explain:

• The problem your group studied.
• The decision and optimization versions of the problem.
• Why the decision version is NP-complete.
• Your brute-force exact algorithm.
• Your bound computations and baseline evaluation.
• Your improved exact algorithm.
• Your approximation method or heuristic.
• Your structured special case, advanced exact-search component, or approved alternative.
• Your reduction experiment.
• Your empirical results and what they show.
• The strengths and weaknesses of your approach.

Students will also critique other groups’ presentations. A good critique asks specific questions about algorithm design, running time, experimental methodology, solution quality, or the interpretation of results. These critiques are part of the project because algorithm design is not only about producing code; it is also about explaining, defending, and evaluating ideas.

Deliverables

Your group will submit the following materials:

• Source code for all implemented exact algorithms and non-exact methods.
• A written explanation of the decision and optimization versions of the problem.
• A verifier and reduction explanation for the decision version.
• A written explanation of the brute-force exact algorithm.
• A written explanation of the bound computations used for evaluation.
• A written explanation of the improved exact algorithm.
• A written explanation of the approximation method or heuristic.
• Experimental runtime data and plots.
• Solution-quality data and plots.
• A discussion of lower or upper bounds used to evaluate solution quality.
• A structured special-case analysis, advanced exact-search analysis, or approved alternative.
• A reduction experiment analysis.
• Final presentation slides.
• Peer critiques of other groups’ presentations.
• Individual contribution summaries.

Checkpoints

This project will be divided into checkpoints. The checkpoints are intended to make progress visible across all roles, not to force the project into a strictly sequential schedule. Several components should be developing at the same time.

A typical checkpoint structure may include:

• Checkpoint 1: Problem selection, responsibility plan, decision/optimization definitions, and initial test-case plan.
• Checkpoint 2: Initial progress from each role: theory outline, brute-force prototype, bound candidates, and heuristic strategy proposal.
• Checkpoint 3: Brute-force exact solver, small-instance ground-truth results, and preliminary bound computations.
• Checkpoint 4: Improved exact solver and initial heuristic implementation.
• Checkpoint 5: Benchmark results, repeated-trial analysis, and reduction experiment plan.
• Checkpoint 6: Structure, tractability, advanced exact search, or reduction experiment results.
• Checkpoint 7: Final presentation, written analysis, and peer critiques.

Rubric

The final project grade will consider both group work and individual contribution. The major grading categories are:

• Correctness and clarity of the decision and optimization problem definitions.
• Explanation of the decision version, verifier, and NP-completeness reduction.
• Correctness and clarity of the brute-force exact solver.
• Quality of the bound computations and baseline evaluation.
• Quality of the improved exact-search method.
• Quality and creativity of the approximation method or heuristic.
• Empirical analysis of running time and solution quality.
• Use of exact optima, lower bounds, or upper bounds to evaluate feasible solutions.
• Analysis of a polynomial-time special case, advanced exact method, or approved alternative.
• Reduction experiment and interpretation.
• Benchmark performance and explanation of results.
• Final presentation quality.
• Peer critique quality.
• Individual contribution and checkpoint participation.

1.1 -

1.2 - 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}.

1.3 - 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}.

1.4 - Project Options

Project Options

MAX 3-SAT

Solve Problem using Independent Set Approximation

For this option, you must develop code that transforms the 3-SAT input into input for the independent set problem (in a polynomial number of steps). Many examples of how to do this are in publication, you just need to implement one of them and discuss how it works.

You can then use the instructor provided approximation algorithm for independent set and compare it to how your team’s approximation method (part D) performs.

Enumerate Clauses and Showcase Results (in development)

For all values of $$3 \ge n \ge 5$$, enumerate all possible input clauses and then show the ratio of unsatisfiable sets versus satisfiable sets.

Max Clique

TSP

Advanced Approximation Strategies

Augment the approximation strategy to:

• Many approximations reach a local min and can’t improve from there. Augment the approximation code to detect this local min and restart the approximation. Track each approximation and show the variance encountered by your program as well as the quality of the best solution as a function of time. Plot these results and discuss.

Longest Path

Test Cases

Generate at least 1000 interesting test cases and perform a comprehensive comparison of how the optimal solution/code differs from the approximation codes results.

Min Vertex Cover

Perform a reduction to Independent Set

For this option, you must develop code that transforms the Min Vertex Cover input into input for the independent set problem (in a polynomial number of steps). Many examples of how to do this are in publication, you just need to implement one of them and discuss how it works.

You can then use the instructor provided approximation algorithm for independent set and compare it to how your team’s approximation method (part D) performs.