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 bit-length 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,n-1), 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 n-1 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 n-1 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.