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

<p>Have a look at the three methods described in this tutorial:
<a href="https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/" rel="nofollow noreferrer">https://www.hackerearth.com/practice/algorithms/graphs/hamiltonian-path/tutorial/</a>
Your DP model solution is option 2.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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?)</p>

<p>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 (<a href="http://www.math.uwaterloo.ca/tsp/concorde.html" rel="nofollow noreferrer">http://www.math.uwaterloo.ca/tsp/concorde.html</a> )</p>

<p>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.)</p>

CC BY-SA 3.0
2017-12-08T18:54:21.123Z
Just to be explicit on how to use a TSP solver for HAMP PATH: for a given instance of your HAM PATH problem, add a new dummy node with weight 1 edges to every node in your graph. Find a TSP solution using state-of-the-art software, and then remove that dummy node (subtracting 2 from the total weight). Note that CONCORDE has solved instances of TSP with over 80,000 nodes.
JimN
CC BY-SA 3.0
2017-12-09T18:27:59.023Z
Excellent answer! Thank you very much, JimN.
f10w
CC BY-SA 3.0
2017-12-10T16:16:52.420Z
I've implemented the dynamic programming approach but it is really not practical at all for a high number of nodes. I'm now trying DFS. In the above tutorial (that you gave the link), the problem being solved is checking whether a Ham Path exists. I'm trying to apply it to finding the shortest Ham Path, but this does not seem so obvious, since the DFS search does not find ALL Ham Paths (even with multiple starts from all nodes) . For example, suppose that during DFS I have found a (partial) path (0) -- (i) -- (j), then all these three nodes are in stack and therefore... (continued next)
f10w
CC BY-SA 3.0
2017-12-10T16:17:52.860Z
and therefore the edge (0) -- (j) will never be considered (assume that it exists). Am I right? Do you have any suggestions for that? Thanks.
f10w
CC BY-SA 3.0
2017-12-10T19:29:23.033Z
The DFS approach could backtrack and attempt every possible next-vertex choice. So in your example, if some HAM path was found starting with 0-i-j it will continue  searching all of them until all the 0-i-j-x have been checked, then it will try 0-j- if j is a neighbour of 0, and it should check every 0-y- for each y neighbour of 0. As these paths are extended, if they exceed the path found in 0-i-j- then that branch can end.
JimN
CC BY-SA 3.0
2017-12-10T19:32:31.947Z
If your edge weights have a minimum (of 1 or higher) then you can cut the search branch earlier by knowing that if you have used 50 out of 90 nodes with a path-so-far length of 65 and the best HAM PATH you found so far is 75, then since you have 40 nodes left to go, your path-so-far of 65 must take on at least an additional length of 40-1, making it way worse than 75, so this branch could have been cut long ago. There are many additional heuristics you can add to cut your branches earlier. e.g. instead of estimating the path-length remaining via the minimum edges, you could precompute dijkstra
JimN
CC BY-SA 3.0
2017-12-08T18:48:48.867Z
2017-12-08T18:48:48.867Z
JimN
<p>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.</p>

<blockquote>
  <p>David Eppstein:<br>
  The Traveling Salesman Problem for Cubic Graphs.<br>
  J. Graph Algorithms Appl. 11(1): 61-81 (2007)</p>
</blockquote>

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

CC BY-SA 3.0
2017-12-07T13:53:25.880Z
Thanks, but this result is not applicable to the SHP problem, isn't it? One can convert the SHP to the TSP by adding a dummy node, but the max degree in the new graph is no longer 3 :(
f10w
CC BY-SA 3.0
2017-12-07T06:10:21.910Z
2017-12-07T06:10:21.910Z
Gamow
<p><strong>Problem:</strong> <em>Given a positive-weighted undirected graph, find the shortest path (in terms of total sum of edges) that visits each node exactly once.</em></p>

<p>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$.</p>

<p>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).</p>

<p>However, if the graph is very sparse (e.g. a node has only a few neighbors), then one <strike>would expect these complexities to drop significantly</strike> 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. <strong>I am looking for practical algorithms/implementations that do not necessarily have lower theoretical complexities</strong> 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.</p>

<p>Thank you in advance for your help!</p>

CC BY-SA 3.0
2017-12-07T03:38:34.897Z
_one would expect these complexities to drop significantly_ — One would? Why? There are still 2^n subsets of vertices, and for most of them, there are still at least n/2 choices for last vertex.
Jeffε
CC BY-SA 3.0
2017-12-07T14:08:33.933Z
@Jeffε I don't have a rigorous argument yet, but if the graph is very sparse than most of the elements of $D$ is $+\infty$ and I guess we don't need to store or compute them.
f10w
CC BY-SA 3.0
2017-12-07T20:35:19.307Z
It is hard to determine whether you are looking for provable upper-bounds on the runtime in terms of some density measure, or a practical algorithm which might be computationally feasible, but we can't prove it to be better than the runtime you gave. It's also not clear whether such algorithm needs to detect whether a HAM PATH exists, or if we are given that a HAM PATH exists and we have to find the cheapest one. Can you clarify these two?
JimN
CC BY-SA 3.0
2017-12-08T18:02:20.487Z
@JimN Thanks. Very good points! I'm looking for a practical algorithm/implementation (whose theoretical complexities are not necessarily lower than the above). And if this algorithm can check if a Hamiltonian path exists before finding the shortest, then it's certainly better!
f10w
<graph-algorithms><co.combinatorics><shortest-path>
How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?
f10w
# How to solve the Shortest Hamiltonian Path problem on Sparse Graphs?

(Asked by: username_0 on 2017-12-07)

**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!

**Tags:** graph-algorithms, co.combinatorics, shortest-path

> **Comments:**
> **username_1**: _one would expect these complexities to drop significantly_ — One would? Why? There are still 2^n subsets of vertices, and for most of them, there are still at least n/2 choices for last vertex.  
> **username_0**: @username_1 I don't have a rigorous argument yet, but if the graph is very sparse than most of the elements of $D$ is $+\infty$ and I guess we don't need to store or compute them.  
> **username_2**: It is hard to determine whether you are looking for provable upper-bounds on the runtime in terms of some density measure, or a practical algorithm which might be computationally feasible, but we can't prove it to be better than the runtime you gave. It's also not clear whether such algorithm needs to detect whether a HAM PATH exists, or if we are given that a HAM PATH exists and we have to find the cheapest one. Can you clarify these two?  
> **username_0**: @username_2 Thanks. Very good points! I'm looking for a practical algorithm/implementation (whose theoretical complexities are not necessarily lower than the above). And if this algorithm can check if a Hamiltonian path exists before finding the shortest, then it's certainly better!  

---

## 2 answers

### Answer by username_2 on 2017-12-08. Score: 3 | Accepted answer

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.)

> **Comments:**
> **username_2**: Just to be explicit on how to use a TSP solver for HAMP PATH: for a given instance of your HAM PATH problem, add a new dummy node with weight 1 edges to every node in your graph. Find a TSP solution using state-of-the-art software, and then remove that dummy node (subtracting 2 from the total weight). Note that CONCORDE has solved instances of TSP with over 80,000 nodes.  
> **username_0**: Excellent answer! Thank you very much, username_2.  
> **username_0**: I've implemented the dynamic programming approach but it is really not practical at all for a high number of nodes. I'm now trying DFS. In the above tutorial (that you gave the link), the problem being solved is checking whether a Ham Path exists. I'm trying to apply it to finding the shortest Ham Path, but this does not seem so obvious, since the DFS search does not find ALL Ham Paths (even with multiple starts from all nodes) . For example, suppose that during DFS I have found a (partial) path (0) -- (i) -- (j), then all these three nodes are in stack and therefore... (continued next)  
> **username_0**: and therefore the edge (0) -- (j) will never be considered (assume that it exists). Am I right? Do you have any suggestions for that? Thanks.  
> **username_2**: The DFS approach could backtrack and attempt every possible next-vertex choice. So in your example, if some HAM path was found starting with 0-i-j it will continue  searching all of them until all the 0-i-j-x have been checked, then it will try 0-j- if j is a neighbour of 0, and it should check every 0-y- for each y neighbour of 0. As these paths are extended, if they exceed the path found in 0-i-j- then that branch can end.  
> **username_2**: If your edge weights have a minimum (of 1 or higher) then you can cut the search branch earlier by knowing that if you have used 50 out of 90 nodes with a path-so-far length of 65 and the best HAM PATH you found so far is 75, then since you have 40 nodes left to go, your path-so-far of 65 must take on at least an additional length of 40-1, making it way worse than 75, so this branch could have been cut long ago. There are many additional heuristics you can add to cut your branches earlier. e.g. instead of estimating the path-length remaining via the minimum edges, you could precompute dijkstra  

---

### Answer by username_3 on 2017-12-07. Score: 4

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)$.

> **Comments:**
> **username_0**: Thanks, but this result is not applicable to the SHP problem, isn't it? One can convert the SHP to the TSP by adding a dummy node, but the max degree in the new graph is no longer 3 :(  

---

