Reading

These notes and Unit 6 sections 2 and 3.

Quiz questions

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

What's it all mean?

Since we have a polynomial time reduction of HAM_CYCLE to LONG_PATH,