> Regarding your initial idea. That is called a bi-directional search and was my first inclination too assuming only the shortest path(s) were desired. Unfortunately, if there is a 3 node solution and a 7 node solution, neversaint wants both.

yes but IMHO it's still applicable for "all paths", you just have to test combinations of "half paths" that meet in a node.

IMHO that should already reduce the complexity C(n) of a uni-directional approach to 2*C(n/2) of bi-directional, which means a dramatical speed up!

> Here is an actual example - one that I tested with:

>      L     F       B
>    / | \ /  \    / | \
>   R--J--X----D--Q  P  M
>    \ | /         \ |  |
>      Z             U--S
[download]

The point here is that the (one element) set of edges {(D,Q)} is already a min-cut of the graph which separates start and stop.

Sorry it's been 15 years now since I heard (the basics) of graph theory at uni but IMHO calculating the shortest path should be a good start for identifying cuts.