Randomized algorithm for finding hamiltonian path in a directed graph

Question

From this Wikipedia article:

http://en.wikipedia.org/wiki/Hamiltonian_path_problem

A randomized algorithm for Hamiltonian path that is fast on most graphs is the following: Start from a random vertex, and continue if there is a neighbor not visited. If there are no more unvisited neighbors, and the path formed isn't Hamiltonian, pick a neighbor uniformly at random, and rotate using that neighbor as a pivot. (That is, add an edge to that neighbor, and remove one of the existing edges from that neighbor so as not to form a loop.) Then, continue the algorithm at the new end of the path.

I don't quite understand how this pivoting process is supposed to work. Can someone explain this algorithm in more detail? Perhaps we can eventually update the Wiki article with a more clear description.

Edit 1: I think I understand the algorithm now, but it seems like it only works for undirected graphs. Can anyone confirm that?

Here's why I think it only works for undirected graphs:

alt text http://www.michaelfogleman.com/static/images/graph.png

Pretend the vertices are numbered like so:

123
456
789

Let's say my path so far is: 9, 5, 4, 7, 8. 8's neighbors have all been visited. Let's say I choose 5 to remove an edge from. If I remove (9, 5), I just end up creating a cycle: 5, 4, 7, 8, 5, so it seems I have to remove (5, 4) and create (8, 5). If the graph is undirected, that's fine and now my path is 9, 5, 8, 7, 4. But if you imagine those edges being directed, that's not necessarily a valid path, since (8, 5) is an edge but (5, 8) might not be.

Edit 2: I guess for a directed graph I could create the (8, 5) connection and then let the new path be just 4, 7, 8, 5, but that seems counter productive since I have to chop off everything that previously led up to vertex 5.

Answer 1

It is indeed a very unclear explanation, and the algorithm does not seem to come from any of the listed references either.

The idea seems to be to first make a random path by picking the initial node at random and proceeding from that by selecting random neighbors for as long as that is possible. When no more neighbors can be picked, either the path is Hamiltonian or it is not. If it is not, this last node on the path has some neighbor already on the path (see below), so the pivoting means to make an edge from the last node to the neighbor already on the path and deleting one of the links from the neighbor that have been chosen for the path. Then, there is a new end to the path, from which the process is continued.

It seems this algorithm assumes, for instance, that there are no nodes with only a single edge. These are easy to cover, though: if there is one of them, just start from that, if there are two, start from one of them and try to end up at the other, and if there are more than two, there cannot be a Hamiltonian path.

Answer 2

Basically, once your random selection of nodes has construct a graph in such a way that the last vertex A has no unvisited neighboring vertices you need to make a vertex available to continue on.

To do this: select a neighboring vertex at random, remove one of its existing edges (in a Hamiltonian path there can be only two edges from any single vertex), then draw a new edge from your current vertex to this now available randomly selected one. You then trace from the randomly selected vertex to the end of the graph (the first vertex that has only a single edge leaving it) and continue the algorithm.

In all sorts of horrific psuedo-code:

  Graph graph;
  Vertex current;
  Path path;

  while(!IsHamiltonian(path))
  {
    if(HasUnvisitedNeighbor(current, path))
    {
      Vertex next = SelectRandomUnvisited(current, path);
      DrawEdgeTo(next, current, path);
      current= next;
    }
    else
    {
       Vertex next = SelectRandomNeighbor(current, path);
       RemoveRandomEdgeFrom(next, path);
       DrawEdgeTo(next, current, path);
       path = FindEnd(next, current, path);  //Finds the end of the path, starting from next, without passing through current
    }
  }