Escape from Exponential Island

Cartoon illustration of students approaching Exponential Island, where signs show brute force, pruning, complexity, local optima, and several NP-complete problem choices.
Explore exact search, pruning, bounds, and heuristics for NP-complete problems.

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:

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:

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:

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

Baseline Exact Search and Bound Computation Lead

Improved Exact Search and Pruning Lead

Heuristic Search and Benchmark Lead

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:

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:

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:

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.

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:

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:

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:

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:

Possible special cases include:

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:

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:

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:

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:

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:

Rubric

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