Can anyone suggest an algorithm for this problem.

Given an undirected unweighted cyclic graph, and a given start and end node in that graph, I’d like to determine if there is *exactly one* valid path from start to end visiting all nodes (i.e. a Hamiltonian path, not a cycle).

It’s NP-hard, but my N is relatively small (up to 30 nodes or so) and each node’s connectivity is typically very small (no more than 4-5, often 2 or 3, typically local links [i.e. they correspond to locations in 2d connected to near neighbours]), so I’m confident it is feasible.

Published algorithms are typically for cycles, for finding a single solution, and for unknown start and end points. I’m curious if anyone can suggest something more fitting, or if you have any intuition on an approach.

2

If the problem is small enough, a totally naive approach works well. We want to generate all *pinned* hamiltonian paths connecting two nodes *a* and *b* in a given *graph*. For this, we just generate all valid paths originating from *a* and filter out those that are not hamiltonian or that do not end in *b*.

The following code snippet is an implementation of this idea in OCaml. On my machine it can find all pinned hamiltonian path in a complete graph of size 9 (there is (9-2)! = 5040 such paths, they are all the permutations of 7 non-pinned nodes), but the program cannot handle the case of size 10. This should give you an idea of the complexity of the operation, but as you see, I could not be less naive when implementing this.

```
module Graph =
struct
type t = {
node: int list;
edge: (int * int list) list;
}
let nodes graph =
List.sort_uniq Pervasives.compare graph.node
let neighbours graph n =
try List.assoc n graph.edge
with Not_found -> []
let pointed_hamiltonian_paths graph a =
let is_visiting_all_nodes path =
let sort = List.sort Pervasives.compare in
sort path = sort graph.node
in
let hamiltonian_extensions path =
match path with
| [] -> []
| node :: _ ->
match List.filter
(fun x -> not(List.mem x path))
(neighbours graph node)
with
| [] -> [ path ]
| newnodes -> List.map (fun x -> x :: path) newnodes
in
let rec loop paths =
match List.concat (List.map hamiltonian_extensions paths) with
| [] -> []
| newpaths ->
if newpaths = paths then paths else loop newpaths
in
List.filter is_visiting_all_nodes (loop [[a]])
let pinned_hamiltonian_paths graph a b =
List.filter (fun path -> (match path with hd ::_ -> hd = b | [] -> false))
(pointed_hamiltonian_paths graph a)
let example_1 = {
node = [1; 2; 3; 4; 5];
edge = [
1, [ 4 ];
2, [ 4; 5];
3, [ 5 ];
4, [ 1; 2; 5 ];
5, [ 2; 3; 4 ];
];
}
let example_2 = {
node = [ 6; 7; 8 ];
edge = [
6, [ 7; 8];
7, [ 6; 8];
8, [ 6; 7];
];
}
let example_3 = {
node = example_1.node @ example_2.node;
edge = example_1.edge @ example_2.edge;
}
let complete n =
let rec loop ax i =
if i < 1 then ax else loop (i :: ax) (pred i)
in
let seq = loop [] n in {
node = seq;
edge = List.map (fun x -> x, seq) seq;
}
end
```

There are three examples of graphs defined, the first one is:

the second one is a complete graph without loops (edges having the same start and end points) and the third one is the disjoint union of the two. With these definitions we can experiment a bit in the toplevel:

```
# Graph.pinned_hamiltonian_paths Graph.example_1 1 3;;
- : int list list = [[3; 5; 2; 4; 1]]
# Graph.pinned_hamiltonian_paths Graph.example_2 6 8;;
- : int list list = [[8; 7; 6]]
# Graph.pinned_hamiltonian_paths Graph.example_3 1 3;;
- : int list list = [] (* The graph is not connected! :) *)
# Graph.pinned_hamiltonian_paths (Graph.complete 4) 1 4;;
- : int list list = [[4; 3; 2; 1]; [4; 2; 3; 1]]
```