8. Coping with NP-Hardness

Having discussed a range of advanced techniques to obtain polynomial-time algorithms for various graph problems beyond the scope of an introductory algorithms class, we leave the realm of problems that can be solved in polynomial time and focus on techniques for solving NP-hard problems now. We will focus almost exclusively on NP-hard optimization problems.

In this chapter, we use the vertex cover problem as an introductory example to highlight some of the central challenges and techniques for coping with NP-hardness. After this brief overview given in this chapter, the remaining chapters in these notes discuss a range of techniques that can be used to design approximation algorithms and techniques for designing fast exponential-time algorithms to solve NP-hard optimization problems.