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.

Galacto

Hamiltonian path's exist (by definition) on undirected graphs. Any algorithms that find them must thereby operate on undirected graphs. – Annalee

Well, the Wikipedia article said: "the Hamiltonian path problem and the Hamiltonian cycle problem are problems of determining whether a Hamiltonian path or a Hamiltonian cycle exists in a given graph (whether directed or undirected)." Basically I'm looking for the longest simple path (no vertices visited more than once) I can find in a directed graph. Now it seems that this algorithm won't help me. – Galacto

Inconsistency in Wikipedia: "... a Hamiltonian path (or traceable path), is a path in an undirected graph which visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle in an undirected graph which visits each vertex exactly once...". – Annalee

Upon further reflection, this algorithm may still work for directed graphs. Consider that the notion of the neighbors of vertex A is interpreted as "all vertices X for which an edge A -> X exists". – Annalee

Right, but then how do we implement FindEnd as you called it in your pseudo-code? See my Edit 2. – Galacto

I would guess that when you are selecting the node to pivot, you would need to discard nodes where you don't get a path after removing one edge, since in a directed graph, there is only one edge you can remove and still keep the path structure, and if that creates a cycle, it's not usable. – Aeroplane

I've implemented this algorithm. It is attributed to Angluin and Valiant (1979) in a book by Wilf: math.upenn.edu/~wilf/AlgoComp.pdf . (Found on MathWorld: mathworld.wolfram.com/HamiltonianPath.html .) – Whereto

Pseudocode is on page 121 of that book. Note that the algorithm given there is a little different; it's guaranteed to terminate but may fail to find a solution even if one exists. It's only "almost certain" to find the solution, and then only if the graph has a lot of edges! By contrast, the algorithm as described by Wikipedia will wander forever if no Hamiltonian path exists. Hey, what can you expect of an O(n^2) algorithm for an NP-complete problem? – Whereto

@Kevin Montrose: The algorithm relies on being able to pivot, which reverses part of the path. So no, I don't think it would work for a directed graph. – Whereto

One last thing to point out: If you only let one end of the path wander, then a bad initial choice can condemn you never to find a solution. (Or at least to wander for a really long time. Learned that one the hard way!) So at some point you must switch to the other end of the path and let that end wander for a while. Or make sure you pick a good starting node. – Whereto

Answer 1

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
    }
  }

Annalee

RemoveRandomEdgeFrom(next, path); DrawEdgeTo(next, current, path); can result in a loop. You can't just remove an edge at random. You have to remove the edge that's closest to current. – Whereto

I'm accepting this answer since the pseudo-code was helpful in understanding the algorithm, although we found that it only works for undirected graphs. – Galacto

Answer 2

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.

Aeroplane

Answer 3

Do you understand what an edge is? If the vertices are v1, v2, .. vn, then an edge is a pair (v1, v2) - imagine drawing a line between v1 and v2, and that is an edge.

So, basically you do a basic hill-climbing algorithm (keep adding edges and visiting unvisited nodes) subject to the constraint that you don't visit a node more than once.

And if you find you can't continue any more (can't reach any more of the unvisited nodes from the current vertex), then you choose a random vertex which is connected (there is an edge between that vertex and one of the vertices that you have visited already) and add in an edge between that vertex and the visited nodes that is not already in the path.

This might (and possibly must, leave that up to the mathematicians) create a loop. You can remove the loop by removing another edge from the edges in the path.

Basically, this is a hill-climbing algorith, with a bit of randomized perturbation when you get stuck. When you get stuck, you basically add in another edge and remove one from the graph and try continuing. If you were completely wrong, you can still get to a solution because in theory you could add in all the right edges and delete all of your original wrong choices.

Gooey