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 ( k n ( m + n log ⁡ n ) ) and the fastest algorithm is due to Gotthilf and Lewenstein (2009) with time complexity in O ( k n ( m + n log ⁡ log ⁡ n ) ) . For bounded treewidth graphs, Eppstein and Kurz (2017) lowered the computational complexity to O ( k n ) by retrieving paths from the k smallest solutions of a monadic second-order formula, and to O ( n + k log ⁡ ( 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 ( k n ) time on bounded treewidth graphs.