Class 37: NP-Complete Problems Everywhere!


Reading
Section 34.5 of Introduction to Algorithms.

Homework
None.

Homework Review
We reviewed the homework that was due today, which was to give a polynomial time reduction of SET-PARTITION to SIMPLE-KNAPSACK. That means:

  1. Clearly state an algorithm that takes an instance of SET-PARTITION as input and produces an equivalent instance of SIMPLE-KNAPSACK in polynomial time.
  2. Prove that the input and output instances for your algorithm really are equivalent.
  3. Prove that the algorithm really takes polynomial time.

Proving SAT is NP-Complete
The SAT problem is this: Gvien a boolean formula, determine whether it is satisfiable. In other words, given a boolean formula in the variables x1,x2,...,xk, is there an assignment of true/false values to the variables for which the formula evaluates to true?

We don't need to go through the same kind of pain as last class. We don't need to show explicitly how to transform an instance of any problem in NP directly into a SAT problem. Instead we need only show how to polynomial time reduce any CIRCUIT-SAT instance to an instance of SAT. Why? Because we know that any problem in NP can be polynomial-time reduced to an equivalent CIRCUIT-SAT instance, and if we can reduce that to an equivalent SAT instance in polynomial time, we'll have an instance of SAT that is equivalent to our original problem instance, and we will have gotten it in polynomial time.

We did this reduction in class. Rather than write it again here, I refer you to pages 996-998 in the textbook.

A Menagerie of Well-Known NP-Complete Problems
Page 1004 of the textbook Gives a diagram showing several well-known problems and the sequence of reductions from CIRCUIT-SAT that proves them to be NP-Complete. The problem descriptions and the reductions are in the book. You are responsible for knowing what these problems are!

Note 1: What the book calls "vertex cover" differs from the problem we've been calling "vertex cover". Given a graph G and a set C of vertices in G, C is a book's-vertex-cover of G if for every edge in G one or both of its endpoints are in C. C is a our-vertex-cover of G if every vertex in G is either in C or connnected by an edge to an element of C.

Note 2: What the book calls "SUBSET-SUM" is the problem we've been calling "SIMPLE-KNAPSACK".

Proving Our-Vertex-Cover is NP-Complete
To prove that our-vertex-cover is NP-Complete, we need to polynomial-time reduce a known NP-Complete problem to it. I will reduce book's-vertex-cover to our-vertex-cover.
Algorithm: Polynomial time reduction of book's-vertex-cover to our-vertex-cover
Input: graph G and integer k, 0 < k ≤ |G|
Output: graph G' and integer k such that there is a book's-vertex-cover of G in k vertices if and only if there is an our-vertex-cover of G' in k vertices.
  1. let G' be a copy of G
  2. for each edge (u,v) in G, add a new vertex w and new edges (u,w) and (w,v) to G'.
  3. return G',k
This algorithm clearly can be done in polynomial time. The interesting thing is to prove that the input and output problem instances are equivalent. As always, this means proving two things [note: to make the discussion easier, let's assume that there are no isolated vertices in G, i.e. there are no vertices that are completely without edges]:

Part 1: If there is a book's-vertex-cover of G in k vertices, there is an our-vertex-cover of G' in k vertices
Proof:

Part 2: If there is an our-vertex-cover of G' in k vertices, there is a book's-vertex-cover of G in k vertices
Proof:

A Brief Discussion of Approximation Algorithms
At this point we've seen that there are lots of NP-Complete problems. Moreover, unless the collective intuition of the large CS community is wrong (i.e. P is equal to NP), there are no fast algorithms for solving these problems. So where does that leave us when we need to deal with one of these problems. You basically have two options.

  1. Give up on getting a fast algorithm. Use an exponential time algorithm and hope for the best. Maybe your problem instances will be small enough and you'll be OK. Maybe for the problems that come up in your application the exponential worst case behaviour won't exhibit itself. Clearly this is not a very desireable situation, but ...
  2. Give up on getting optimum solutions and try to just get "pretty good" solutions in a reasonable amount of time. An algorithm that settles for finding "pretty good" solutions to an NP-Hard optimization problem in polynomial time is called an approximation algorithm. Chapter 35 in your textbook is dedicated to this.


Christopher W Brown
Last modified: Fri Apr 23 11:59:13 EDT 2004