3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jeffε Dec 7 '17 at 3:38
  • $\begingroup$ @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. $\endgroup$ – Khue Dec 7 '17 at 14:08
  • $\begingroup$ 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? $\endgroup$ – JimN Dec 7 '17 at 20:35
  • $\begingroup$ @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! $\endgroup$ – Khue Dec 8 '17 at 18:02
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – JimN Dec 8 '17 at 18:54
  • $\begingroup$ Excellent answer! Thank you very much, JimN. $\endgroup$ – Khue Dec 9 '17 at 18:27
  • $\begingroup$ 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) $\endgroup$ – Khue Dec 10 '17 at 16:16
  • $\begingroup$ 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. $\endgroup$ – Khue Dec 10 '17 at 16:17
  • $\begingroup$ 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. $\endgroup$ – JimN Dec 10 '17 at 19:29
4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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 :( $\endgroup$ – Khue Dec 7 '17 at 13:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.