How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

Question

Problem: Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once.

For a subset $S$ of nodes and a node $i\in S$, let $D[S][i]$ denote the length of the shortest path within $S$ that ends at $i$.

A common solution to the SHP problem is using dynamic programming for computing $D[S][i]$ for all subsets $S$ and all nodes $i$. If $n$ is the number of nodes then the time and memory complexities of this solution are respectively $\mathcal{O}(2^nn^2)$ and $\mathcal{O}(2^nn)$, which is not feasible for large graphs (having $100$ nodes for example).

However, if the graph is very sparse (e.g. a node has only a few neighbors), then one would expect these complexities to drop significantly would expect the above solution to be practical. I would appreciate a lot if somebody can give me some insights on how to solve/implement the SHP for very sparse graphs. I am looking for practical algorithms/implementations that do not necessarily have lower theoretical complexities and if they can also check if a Hamiltonian path exists before finding the shortest one (and still remaining practical), then that would be great.

Thank you in advance for your help!

Answer 1

Considering your response in the comments where you do not necessarily need a provably-better runtime:

Have a look at the three methods described in this tutorial: https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/ Your DP model solution is option 2.

With a sparse graph, a large number of subgraphs will not be connected and so many entries of the DP table could be filled with a trivial 'false' (or +infinity in the case of maintaining path costs) without having to compute subproblems. More explicitly, let $G[S]$ be the subgraph of $G$ induced on vertex set $S$ and $N(v)$ be the open neighbourhood of $v$, then for every $v$, $v \cup G[V-N(v)]$ is not connected and so has no Ham Path. When $N(v)$ is small, these subgraphs are large, and could translate to a lot of savings when trying to fill the DP table in a top-down-with-memoization order.

In the link's solution (3), DFS with backtracking is suggested which might make more sense in your case as you are looking for the shortest path rather than the existence of a path. A small vertex degree creates less branching in this search, and with an objective function in mind, it gives you the additional savings of an easy way to prune your search once your dfs-path-so-far sum exceeds the best-path-sum-found-so-far.

In this DFS version, you enjoy the lower branch factor just by the inherent structure of the sparse graph (you might want to include a tie-breaking rule to choose vertices of lowest degree). In the DP solution, you have to add extra code to an existing DP-solution to enjoy those sparsity benefits.

In this HAM PATH problem, if you ever have a vertex of degree 2, note that you MUST include those two edges on that vertex in your potential solution (at that stage of the backtracking). In exponential-time algorithms, any amount of forced choices you can add will help the runtime. In the DFS approach, as you place vertices in your DFS stack, they can be considered removed from the graph, which deletes edges and further enforces sparsity in the remaining graph, so searching for newly-created degree-2 vertices is in your best interests.

There are many more local configurations that lead to forced edges and/or the decision that there is no HAM PATH which might exist more often in sparse graphs (how sparse are we talking here?)

If you are in need of a practical solution, whether or not you are exploiting the sparsity of the graph, you might want to consider some prebuilt solutions like CONCORDE (http://www.math.uwaterloo.ca/tsp/concorde.html )

Also, if you are running many of these, there is a large body on algorithms applying to random graphs that solve HAM PATH with high probability.)

Answer 2

Indeed: Eppstein has shown that the TSP can be solved in time $O(1.26^n)$ if all vertices are of degree at most 3.

David Eppstein:
The Traveling Salesman Problem for Cubic Graphs.
J. Graph Algorithms Appl. 11(1): 61-81 (2007)

Some tiny improvements of this result are also known, for instance by Liśkiewicz and Schuster (2014) to $O(1.255^n)$.