Reading
These notes and
Unit 6 sections 2 and 3.
Quiz questions
 P4
from Week 11 quiz
questions (yes, I know that we're in Week 12 now, but I
don't want to have just one problem for week 12).
This should be done efore Class 31.
The Problem
This class was all about providing a polynomial time reduction
of HAMCYCLE(G) to LONGPATH(G,k). Here are the definitions of
the problems:
 HAMCYCLE(G)

Is there a "Hamiltonian Cycle" in graph G, i.e. a cycle that
visits every node in the graph. A cycle is a list of vertices
in which each pair of consecutive vertices is connected by an
edge, there are no repetitions, and there is an edge from the
last vertex to the first.
 LONGPATH(G,k)

Is there a path in graph G of length at least k?
So, we need to devise an algorithm that takes an instance of
HAMCYCLE(G) and produces an instance of LONGPATH(G,k) such
that:
1) the algorithm runs in time polynomial in the bitlength of
the HAMCYCLE(G) problem instance, and 2) the answer to the two
instances are the same  i.e. the answers to both are TRUE or
the answers to both are FALSE.
First Attempt
Out first attempt is to simply take the input instance
HAMCYCLE(G) and produce the out LONGPATH(G,n1), where G has n
vertices. [Note: we're defining the length of the path to be the
number of edges in the path.]
If there is a Hamiltonian cycle in G, there is a
path of length n1 in G ... just remove one edge of the cycle
and you get the path. However, there are some situations in
which there is a path of length n1 in G, but no Hamiltonian
cycle, so our First Attempt Algorithm does not always produce
equivalent instances. Example: The "bowtie graph" we
discussed in class.
Second Attempt
Clearly, the graph we use for LONGPATH is going to have to be
different from G. My suggestion was this: We failed in the
First attempt because we might have paths that start and end at
vertices that are not connected by an edge. Therefore we can't
"close the loop" to get a cycle. So let's force a situation
where "closing the loop" can occur. What I suggested was to
pick a random vertex in G, call it u, and create a new vertex
u' that is a copy of u, meaning that it has all the same
neighbors. This gives us a new graph G' with n+1 vertices. If
there is a path of length n from u to u' in graph G', then we
can "merge" u and u' to recover graph G, and the path in G'
becomes a Hamiltonian cycle in G.
Unfortunately, we found a problem here too, because it may be
that there are paths of length n in G', but that none of them
are from u to u'.
Third Time's a Charm
So what we need to do is to follow the idea fromthe Second
Attempt, but somehow force any sufficiently long path to start
at u and end at u'. The key observation is that if there is a
vertex in a graph that has only one neighbor, it must be either
the start or end vertex in any path visiting it. So we add new
vertices v and v', which are only connected by an edge to u and
u', respectively. Now, any path of length n+2 in this graph
(i.e. which visits every node) must start at v, then go to u,
and end up by visiting u' and then taking its last step to v'.
If G' is the name of this newe graph, then HAMCYCLE(G) is true
if and only if LONGPATH(G',n+2) is true.
Proof that problem instances are equivalent

If G has a Hmiltonian cycle, then C' has a path of length
n+2.
The proof is pretty straightforward. If G has a hamiltonian
cycle, then we can list the elements of the cycle, in order,
starting from any vertex we like. So let's start listing
them from u. So, letting v1 = u, the Hamiltonian cycle in G
is:
v1 → v2 → ... → vn → v1
Thus, the following must be a valid path of length n+2 in G':
v → v1 → v2 → ... → vn → u' → v'
QED

If G' has a path of length n+2, then C has a Hamiltonian cycle
Once again, the proof is pretty straightforward. If G' has
a path of length n+2, the path must start at v and end at
v', since they have only one neighbor each.
(It could start at v' and end at v, but then we could simply
reverse it to get a path that starts at v and ends at v'.)
Moreover, the vertex following v must be u and the vertex
preceeding v' must be u'. So, the path looks like the
following (where v1 = u):
v → v1 → v2 → ... → vn → u' → v'
Since u' and u (and remember u=v1) have the same neighbors,
the following is a cycle in G:
v1 → v2 → ... → vn → v1
Since all vertices of G are in this cycle, it must be a
Hamiltonian cycle. QED
What's it all mean?
Since we have a polynomial time reduction of HAM_CYCLE to LONG_PATH,

a polynomial time algorithm for solving LONG_PATH (if we ever
found one!) would immediately provide us with a polynomial time
algorithm for solving HAM_CYCLE, and

a proof that HAM_CYCLE could not be solved in polynomial
time (if we could find one) would immediately provide us
with a proof that LONG_PATH cannot be solved in polynomial
time.