Computing shortest paths is one of the central problems in the theory of distributed computing. For the last few years, substantial progress has been made on the approximate single source shortest paths problem, culminating in an algorithm of Henzinger, Krinninger, and Nanongkai [STOC’16] which deterministically computes (1+o(1))-approximate shortest paths in O(D+√n) time, where D is the hop-diameter of the graph. Up to logarithmic factors, this time complexity is optimal, matching the lower bound of Elkin [STOC’04]. The question of exact shortest paths however saw no algorithmic progress for decades, until the recent breakthrough of Elkin [STOC’17], which established a sublinear-time algorithm for exact single source shortest paths on undirected graphs. Shortly after, [FOCS’17] provided improved algorithms for exact all pairs shortest paths problem on directed graphs. In this paper, we provide an alternative single-source shortest path algorithm with complexity O(n3 4D1 4). For polylogarithmic D, this improves on Elkin’s O(n5 6) bound and gets closer to the Ω(n1 2) lower bound of Elkin [STOC’04]. For larger values of D, we present an improved variant of our algorithm which achieves complexity O(max n3 4+o(1) , n3 4D1 6 + D ), and thus compares favorably with Elkin’s bound of O(max n5 6, n2 3D1 3 + D ) in essentially the entire range of parameters. This algorithm provides also a qualitative improvement, because it works for the more challenging case of directed graph (i.e., graphs where the two directions of an edge can have different weights), constituting the first sublinear-time algorithm for directed graphs. Our algorithm also extends to the case of exact r-source shortest paths, in which we provide the fastest algorithm for moderately small r and D, improving on those of
We also show in section:MultipleSources how to extend our algorithm to the case with @math -sources, providing some improvements on the results of @cite_17 for small @math and @math .
@cite_17
2963528540
Subset Sum is a classical optimization problem taught to undergraduates as an example of an NP-hard problem, which is amenable to dynamic programming, yielding polynomial running time if the input numbers are relatively small. Formally, given a set @math of @math positive integers and a target integer @math , the Subset Sum problem is to decide if there is a subset of @math that sums up to @math . Dynamic programming yields an algorithm with running time @math . Recently, the authors [SODA '17] improved the running time to @math , and it was further improved to @math by a somewhat involved randomized algorithm by Bringmann [SODA '17], where @math hides polylogarithmic factors. Here, we present a new and significantly simpler algorithm with running time @math . While not the fastest, we believe the new algorithm and analysis are simple enough to be presented in an algorithms class, as a striking example of a divide-and-conquer algorithm that uses FFT to a problem that seems (at first) unrelated. In particular, the algorithm and its analysis can be described in full detail in two pages (see pages 3-5).