- 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:
- Clearly state an algorithm that takes an instance of
SET-PARTITION as input and produces an equivalent instance
of SIMPLE-KNAPSACK in polynomial time.
- Prove that the input and output instances for your
algorithm really are equivalent.
- 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.
- let G' be a copy of G
- for each edge (u,v) in G,
add a new vertex w and new edges (u,w) and (w,v) to G'.
- 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:
- Let C be the book's-vertex-cover of G in k vertices.
That means that for each edge (u,v) ∈ G,
u ∈ C or v ∈ C.
- Suppose u is a vertex in both G and G'. By our
assumption there is some vertex v in G such that (u,v)
is an edge in G. So u ∈ C or v ∈ C, and
since (u,v) is also an edge in G', that means that
u is either in C or connected by an edge to an element
of C in G'.
- Suppose w is a vertex in G' that corresponds to an
edge (u,v) in G. Since (u,v) is an edge in G, we know
that u ∈ C or v ∈ C. But by the construction
of G', w is connected by an edge to both u and v. So,
w is connected by an edge to an element of C.
- We've shown that every vertex in G' is either in C or
connected by an element of C, and we know that the
size of C is k. Therefore, C is an
our-vertex-cover of G' in k vertices.
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:
- Let C be the our-vertex-cover of G' in k vertices.
That means every vertex in G' is either in C or connected
by an edge to a vertex in C.
- Since C may contain vertices that are not in G (remember
the vertices we added that correspond to edges in G?)
we can't necessarily view C as a potential cover for G.
However, let w be a vertex in G' that corresponds to the
edge (u,v) from G. The only vertices "covered" by w are
w, u, and v. Notice that u and v both cover all three of
these vertices as well. Thus, we can create a new set
C' from C by simply replacing any vertices corresponding
to an edge (u,v) ∈ G with either u or v. C' will
still be a cover in G', but it will contain only vertices
that are also present in G.
- If (u,v) is an edge in G, then there is some vertex w in
G' corresponding to (u,v). Since C' is a cover of G', and
w can't be an element of C', either u or v must be in C'.
Thus, every edge in G has at lest one endpoint in C'.
This means that C' is a book's-vertex-cover of G in k vertices.
- 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.
-
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 ...
-
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.