Chapter 10: Intractable Problems and Approximation Algorithms
In the previous chapters, we have explored a wide variety of algorithms for solving problems efficiently. However, there are many problems for which no efficient algorithm is known. In this chapter, we will discuss the theory of NP-completeness, which provides a way to show that a problem is likely to be intractable, meaning that there is likely no efficient algorithm to solve it. We will also explore techniques for dealing with NP-complete problems, including approximation algorithms and local search algorithms.
P and NP Classes
To understand NP-completeness, we first need to define two important classes of problems: P and NP.
The class P (polynomial time) consists of all decision problems that can be solved by an algorithm that runs in polynomial time. A decision problem is a problem that has a yes-or-no answer. For example, the problem of determining whether a graph has a Hamiltonian cycle (a cycle that visits each vertex exactly once) is a decision problem. If a decision problem is in P, then there is an algorithm that can solve any instance of the problem in a number of steps that is bounded by a polynomial function of the input size.
The class NP (nondeterministic polynomial time) consists of all decision problems for which a solution can be verified in polynomial time. For example, the Hamiltonian cycle problem is in NP because, given a graph and a proposed Hamiltonian cycle, we can easily check in polynomial time whether the proposed cycle is indeed a Hamiltonian cycle.
It is clear that P is a subset of NP, because any problem that can be solved in polynomial time can also be verified in polynomial time. However, it is an open question whether P = NP. Most experts believe that P ≠ NP, meaning that there are problems in NP that are not in P. However, proving this would be a major breakthrough in theoretical computer science.
NP-Completeness
A decision problem X is NP-complete if:
- X is in NP, and
- Every problem in NP is reducible to X in polynomial time.
A problem Y is reducible to a problem X if any instance of Y can be transformed into an instance of X in polynomial time, such that the answer to the instance of Y is "yes" if and only if the answer to the transformed instance of X is "yes".
The concept of NP-completeness was introduced by Stephen Cook and Leonid Levin independently in 1971. The first problem shown to be NP-complete was the Boolean Satisfiability Problem (SAT). Many other problems have since been shown to be NP-complete by reducing SAT or other known NP-complete problems to them.
Some well-known NP-complete problems include:
- The Traveling Salesman Problem (TSP): Given a set of cities and the distances between them, find the shortest tour that visits each city exactly once.
- The Knapsack Problem: Given a set of items with weights and values, and a knapsack with a weight limit, find the subset of items with the maximum total value that fits in the knapsack.
- The Graph Coloring Problem: Given a graph, find the minimum number of colors needed to color the vertices so that no two adjacent vertices have the same color.
The significance of NP-completeness is that if any NP-complete problem could be solved in polynomial time, then all problems in NP could be solved in polynomial time (i.e., P = NP). However, despite decades of effort, no polynomial-time algorithm has been found for any NP-complete problem. This suggests (but does not prove) that NP-complete problems are inherently difficult and are unlikely to have efficient algorithms.
Approximation Algorithms
Since NP-complete problems are believed to be intractable, we often resort to approximation algorithms when faced with such problems in practice. An approximation algorithm is an algorithm that finds a solution that is guaranteed to be within a certain factor of the optimal solution.
For example, consider the Vertex Cover problem: given a graph, find the smallest set of vertices such that each edge is incident to at least one vertex in the set. This problem is NP-complete. However, there is a simple approximation algorithm that finds a vertex cover that is at most twice the size of the optimal vertex cover:
- Initialize an empty set C.
- While there are uncovered edges in the graph:
- Pick an arbitrary uncovered edge (u, v).
- Add both u and v to C.
- Remove all edges incident to u or v from the graph.
- Return C.
This algorithm runs in polynomial time and always finds a vertex cover that is at most twice the size of the optimal vertex cover. To see this, note that in each iteration, the algorithm picks two vertices to cover an edge, while the optimal solution must pick at least one of these vertices. Thus, the algorithm picks at most twice as many vertices as the optimal solution.
Approximation algorithms are often used in practice because they provide a guaranteed level of quality while running in polynomial time. The approximation ratio of an algorithm is the worst-case ratio between the size of the solution found by the algorithm and the size of the optimal solution.
Local Search Algorithms
Another approach for dealing with NP-complete problems is to use local search algorithms. A local search algorithm starts with an initial solution and iteratively improves it by making small local changes until no further improvements can be made.
For example, consider the Traveling Salesman Problem (TSP). A simple local search algorithm for TSP works as follows:
- Start with an arbitrary tour.
- While improvements can be made:
- Consider all possible swaps of two cities in the current tour.
- If any swap improves the tour length, perform the swap.
- Return the current tour.
This algorithm starts with a random tour and repeatedly improves it by swapping pairs of cities, until no further improvements can be made by swapping. The resulting tour is a local optimum, meaning that it cannot be improved by any single swap.
Local search algorithms can often find good solutions quickly, but they are not guaranteed to find the global optimum. They can get stuck in local optima that are far from the global optimum. To mitigate this, various techniques can be used, such as:
- Running the local search multiple times with different initial solutions.
- Allowing the local search to make moves that temporarily worsen the solution, to help escape local optima.
- Using more complex neighborhood structures that consider larger changes to the current solution.
Local search algorithms are widely used in practice for solving large instances of NP-complete problems, often in combination with other techniques such as approximation algorithms and heuristics.
Conclusion
The theory of NP-completeness provides a framework for understanding the inherent difficulty of certain computational problems. NP-complete problems are believed to be intractable, meaning that they are unlikely to have efficient algorithms.
When faced with NP-complete problems in practice, we often resort to approximation algorithms and local search algorithms. Approximation algorithms provide a guaranteed level of solution quality while running in polynomial time. Local search algorithms can often find good solutions quickly by iteratively improving an initial solution.
Understanding the theory of NP-completeness and the techniques for dealing with NP-complete problems is essential for anyone working on real-world optimization problems. While we may not be able to solve NP-complete problems optimally, we can often find good enough solutions using approximation algorithms and local search algorithms.
As the size and complexity of the problems we face continues to grow, the importance of understanding and dealing with NP-completeness will only increase. By mastering the techniques covered in this chapter, you will be well-equipped to tackle some of the most challenging and important problems in computer science and beyond.