Ch.11
Hamiltonian Cyles
Revisited

Remember

Was it fair to say that G transformed to G-> or vice versa?

Yet we could see that it was easier to identify cycles in non-directed so we did want to be able to change from a directed to a non-directed.

Specifically, in order to consider the problem

we had to first make a valid transformation. Only then can we consider whether one problem reduces to the other.

Since we can't do a transformation by using DHC iff UHC directly, we must try an alternate approach.

So, the first thing needed is to define a function f: G-> --> G
that would maintain the information about the direction of arrows on the edges so that we could check back and see if the proper corresponding arrows were used in the determination of the HC.

Is it easy to see that with our transformation, G-> has a HC iff G has a HC?
i.e., that our transformation preserves the information of a HC whether I have direction or not?

For my own ease, let's first just discuss it with only one edge for each vertex: for each u in V, we create (< u,1 >,< u,2 >)

recall

Proof

G-> has a HC => G has a HC

G has a HC => G-> has a HC

At this point, you may ask
Why in class did you show each node become 2 edges? (< u,1 >,< u,2 >,< u,3 >)

Look carefully at the proof above. Are we sure of all of our assumptions? Can you fairly make the assumptions? What assumptions you ask...

Remember how I asked, "Could you give an algorithm for the Hamiltonian Cycle now?"

Note that we could have "neighbors" on the graph that are not on the hamiltonian cycle.
All we showed so far is that G has a HC iff G-> has a HC if the undirected cycle follows the "expected" direction

Since we have no direction anymore we want to make sure that we choose in the undirected graph only valid paths.

Hopefully:      a neighbor on a hamiltonian cycle ==> a neighbor on the graph

consider

Here one goes from a (< p,1 >,< q,2 >) which should be OK but we really want it to go through (< p,1 >,< q,2 >) only where p = q

Now you can't just say in your algorithm that it has to go through (< p,1 >,< q,2 >) such that p = q. Why not? Hints:

  1. remember that this graph is now non-directed. (< p,1 >,< q,2 >) = (< q,2 >,< p,1 >)
  2. Consider a cycle. How do you know if it is a hamiltonian cycle? (We need to verify.)

If we make our path go through (< u,1 >,< u,2 >,< u,3 >) then we are assured that we do not access two edges of the directed graph that were both heads (or tails).

Specifically, now, for our verification, we know we cannot come to (< u,1 >) and leave without going through (< u,2 >). We need this since we can only visit each node once.

If we do this, then we know that any valid hamiltonian cycle will look like
(< u,1 >,< u,2 >,< u,3 >,< v,1 >,< v,2 >, < v,3 >, ...)

The important aspect about the pattern is hence the appearance of < u,2 > since it only exists between < u,1 > and < u,3 >
So, we preserve a direction without "forcing" it since the only way to access the < x,2 > nodes are to go though 1 to 3

Note how this is used in the proof of G has an UHC iff G-> has a DHC

Finally, note that what we did here was take a given directed graph and find a solution for the Hamiltonian Cycle Problem using this transformation. The proof above is not a reduction proof.

How do you show a reduction? UHC DHC ?

Original above example graph

back to the notes