Book Description

Computation of shortest paths is one of the classical problems in theoretical computer science. Given a pair of nodes s and t in a graph G, the goal is to find a path of minimum weight from s to t. Most graphs that commonly occur in practice are sparse graphs. In this work, we deal with several computational problems related to shortest paths in sparse graphs and we present algorithms that provide significant improvements in performance in both sequential and distributed settings. We also present fine-grained reductions that establish fine-grained hardness for several problems related to shortest paths. In the sequential context, we consider the fine-grained complexity of sparse graph problems whose time complexities have stayed at Õ(mn) over the past several decades, where m is the number of edges and n is the number of vertices in the input graph. All of these problems are known to be subcubic equivalent and this shows that achieving sub-mn running time is hard, but only for dense graphs where $m = [Theta] (n2). We introduce the notion of a sparse reduction which preserves the sparsity of graphs, and we present near linear-time sparse reductions between various pairs of graph problems in the Õ(mn) class. We also introduce the MWC-hardness conjecture, which states that Minimum Weight Cycle problem cannot be solved in sub-mn time. We establish that several important graph problems in the Õ(mn) class such as APSP, second simple shortest path (2-SiSP), Radius, and Betweenness Centrality are MWC-Hard, establishing sub-mn fine-grained hardness for these problems. A well-known generalization of the shortest path problem is the k-simple shortest paths (k-SiSP) problem, where we want to find k simple paths from s to t in a non-decreasing order of their weight. In this thesis we present a new approach for computing all pairs k simple shortest paths (k-APSiSP), which is based on forming suitable path extensions to find simple shortest paths; this method is different from the 'detour finding' technique used in all prior work on computing multiple simple shortest paths, replacement paths, and distance sensitivity oracles. The Õ(mn) time bound of our 2-APSiSP algorithm matches the fine-grained time complexity for the simpler 2-SiSP problem, which is the single source-sink version of this problem. Computing APSP is one of the most fundamental problems in distributed computing. We present a simple Õ(n [superscript 3/2]) rounds deterministic algorithm for computing APSP in the well-known CONGEST model which is the first Õ(n2) round deterministic algorithm for this problem. We then improve this further by reducing the round complexity to Õ(n [superscript 4/3]). We also present a faster algorithm for graphs with moderate integer edge weights. We develop several derandomization techniques for our deterministic APSP algorithms. These include efficient deterministic distributed algorithms for computing a small blocker set, which is a set that intersects a desired collection of shortest paths, and several deterministic pipelined approaches for computing the shortest path distance values as well as for propagating the messages in the network. Aside from our deterministic results, all non-trivial distributed algorithms currently known for computing APSP are randomized