Improved algorithms for reachability and shortest path on low tree-width graphs

We consider the reachability and shortest path problems on low tree-width graphs, with n nodes, m edges, and tree-width t, on a standard RAM with wordsize $W$. We use \widetilde{O} to hide polynomial factors of the inverse of the Ackermann function. Our main contributions are three fold: 1. For reachability, we present an algorithm that requires O(n\cdot t^2 \cdot \log(n/t)) preprocessing time, O(n\cdot (t \cdot \log(n/t))/W) space, and O(t/W) time for pair queries and O((n\cdot t)/W) time for single-source queries. Note that for constant t our algorithm uses O(n\cdot \log n) time for preprocessing; and O(n/W) time for single-source queries, which is faster than depth first search/breath first search (after the preprocessing). 2. We present an algorithm for shortest path that requires O(n\cdot t^2) preprocessing time, O(n\cdot t) space, and \widetilde{O}(t^2) time for pair queries and O(n\cdot t) time single-source queries. 3. We give a space versus query time trade-off algorithm for shortest path that, given constant \epsilon>0, requires O(n \cdot t^2) preprocessing time, O(n^{\epsilon} \cdot t^2) space, and \widetilde{O}(n^{1-\epsilon}\cdot t^2) time for pair queries. Our algorithms improve all existing results, and use very simple data structures