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$?

Approximation algorithms

When an NP-complete problem has an optimisation version, we may seek an approximation algorithm: a polynomial-time algorithm whose solution is provably within a constant factor of optimal. The chapter develops the notion of approximation ratio and gives a concrete example.

ApproxVertexCover

A 2-approximation algorithm for minimum vertex cover. The algorithm repeatedly picks an arbitrary uncovered edge $(u, v)$, adds both endpoints to the cover, and removes all edges incident to $u$ or $v$. The resulting cover has at most twice the size of the optimal cover: the picked edges form a matching, and any cover must include at least one endpoint of each matching edge.

Time complexity: $O(n + m)$ — runs in linear time and returns a 2-approximation of the minimum vertex cover.

boolean[] ApproxVertexCover(int[][] adj) {
  int n = adj.length;
  boolean[] C = new boolean[n];
  boolean[] removed = new boolean[n];
  boolean done = false;
  while (!done) {
    done = true;
    int u = 0;
    while (u < n) {
      if (!removed[u]) {
        int v = u + 1;
        while (v < n) {
          if (!removed[v] && adj[u][v] == 1) {
            C[u] = true; C[v] = true;
            removed[u] = true; removed[v] = true;
            done = false; v = n;
          } else { v = v + 1; }
        }
      };
      u = u + 1;
    }
  };
  return C;
}