k-shortest simple paths in bounded treewidth graphs

The k-shortest simple paths problem asks to compute a set of top-k shortest simple paths from a source to a sink in a graph G=(V,E) with |V|=n vertices and |E|=m edges. The most well-known algorithm for solving this problem is due to Yen (1971) with time complexity in O(kn(m+nlog⁡n)) and the fastest algorithm is due to Gotthilf and Lewenstein (2009) with time complexity in O(kn(m+nlog⁡log⁡n)). For bounded treewidth graphs, Eppstein and Kurz (2017) lowered the computational complexity to O(kn) by retrieving paths from the k smallest solutions of a monadic second-order formula, and to O(n+klog⁡(n)) to retrieve the k shortest simple distances only. In this paper, we provide an algorithm that answers k-shortest simple distances in O(k+n) time on graphs with treewidth at most 2, and a constructive algorithm, simpler than that of Eppstein and Kurz, that solves the k-shortest simple paths problem in O(kn) time on bounded treewidth graphs