Chapter 13. Intractability

NP-completeness, polynomial-time reductions, and approximation algorithms.

What is intractability

A problem is intractable if no polynomial-time algorithm can solve it (assuming $P \neq NP$). The theory of NP-completeness provides a framework for classifying problems: a problem is in NP if a proposed solution can be verified in polynomial time, and NP-complete if it is in NP and every problem in NP reduces to it in polynomial time.

Key NP-complete problems

The chapter covers polynomial-time reductions among several central NP-complete problems:

• 3-SAT. Given a CNF formula with exactly 3 literals per clause, determine if it is satisfiable.
• Independent Set. Given a graph $G$ and integer $k$, does $G$ have an independent set of size $k$?
• Vertex Cover. Given a graph $G$ and integer $k$, does $G$ have a vertex cover of size $k$?
• Clique. Given a graph $G$ and integer $k$, does $G$ have a clique of size $k$?
• Subset Sum. Given a set of integers and a target $T$, is there a subset summing to $T$?

Coping with intractability

When a problem is NP-hard, exact polynomial-time solutions aren't available (assuming $P \neq NP$), so the chapter surveys five practical coping strategies, including seeking an approximation algorithm: a polynomial-time algorithm whose solution is provably within a constant factor of optimal. This strategy is developed in depth, with worked examples like ApproxVertexCover, in Chapter 14.