Today we examined one final type of problem reduction: the one-to-many reduction.

The purpose of this type of reduction is the same as the others we have seen: to demonstrate that a new problem is NP-Complete.  The technique is as follows:  
Given a new problem X, we choose a known NP-Complete problem Y and show that Y reduces to X.  So far this is no different from what we have already done.  But instead of showing that we can transform any instance of Y into an instance of X, we show that we can transform any instance of Y into several instances of X.  Answer-preservation in this type of reduction works like this:  If the answer to the instance of Y is YES, then the answer to at least one instance of X is YES.  Similarly, if the answer to at least one instance of X is YES, then the answer to the original instance of Y is YES.  

We defined two problems:

Hamilton Cycle:  Given a graph G on n vertices, is there a cycle in G that contains each vertex exactly once?

Hamilton Path:  Given a graph G on n vertices, is there a path in G that contains each vertex exactly once?

(These  problems are both named after William Hamilton, a mathematician who deserves your interest - look him up.)

Both of these are obviously decision problems, and both are clearly in NP.  

Let us take for granted that Hamilton Cycle (HC) is NP-Complete.  There is actually a very clever reduction from CNF-SAT to HC, but we will not cover it in CISC-365.  We will show that we can use one-to-many reduction to show that Hamilton Path (HP) is also NP-Complete.

First, let's see why we can't just use a one-to-one reduction.  Certainly if a graph has a HC, it also has a HP (just ignore any edge in the HC).  But the YES answer doesn't necessarily carry in the opposite direction: a graph that has a HP need not have a HC.

We might imagine a reduction like this:  Given an instance of HC, delete an edge.  If the resulting graph has a HP, then the original graph does have a HC - just use the deleted edge to close the path and form a cycle.  There are two problems with this:
    - how do we decide which edge to delete?
    - how can we be sure the HP in the derived graph has its ends on the vertices that are joined by the deleted edge?  If it doesn't, then using this edge won't close the cycle.

The first of these questions is what motivates the one-to-many reduction - we create one instance of HP for each edge of the graph (i.e. we create a collection of new graphs, each one the result of deleting a single edge of the original graph).

The second problem is solved by a little trick: in order to make sure that if the derived graph has a HP, then its ends are where we want them to be, we attach two new vertices to the graph, one connected to each end of the edge we are deleting.  Now if the graph has a HP it must start and end at the added vertices (they can't be in the middle of a HP), and the part of the HP that lies in the original graph, plus the deleted edge, form a HC in the original graph.  Thus, if the answer to HP on the constructed graph is YES, the answer to HC on the original graph is YES.

So if the answer to HP on ANY of the constructed graphs is YES, the answer to HC on the original graph is YES.  And if the answer to HC on the original graph is YES, the answer to HP on several of the constructed graphs will be YES.  In this way the transformation is answer-preserving.

But that's only half the story ... the transformation also needs to be polynomial-time.  We can see that it is - each instance of HP that we construct takes only a polynomial amount of time (in fact if we are clever about it, each one can be constructed in constant time from the previous one) and there are only a polynomial number of instances to be constructed.  Thus the total amount of work done during the construction is no more than polynomial time.

The bottom line, as always, is that IF we could find a polynomial time algorithm to solve HP, we could combine it with this one-to-many reduction to create a polynomial time algorithm for HC.  This is all we need to establish that HP is NP-Complete.

We finished the day with the first part of a discussion about an algorithm to solve the Subset Sum problem, but since we didn't finish it until Wednesday, this algorithm will be covered in full in the notes for that day.