In this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms. For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O(m n ). Here we provide the first deterministic algorithm for this problem, with the same O(m n ) time. For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t V and F E V, |F| f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G F ( i.e. , the distance from s to t in the graph G after removing from it the failing edges and vertices F). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented a combinatorial randomized f-DSO with O(mn^ 4- ) preprocessing time and subquadratic O(n^ 2-2(1- ) f ) query time for every value of 0 < < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time.
@cite_30: 
@cite_11: A distance sensitivity oracle is a data structure which, given two nodes s and t in a directed edge-weighted graph G and an edge e, returns the shortest length of an s-t path not containing e, a so called replacement path for the triple (s, t, e). Such oracles are used to quickly recover from edge failures. In this paper we consider the case of integer weights in the interval [-M, M], and present the first distance sensitivity oracle that achieves simultaneously sub cubic preprocessing time and sub linear query time. More precisely, for a given parameter [0, 1], our oracle has preprocessing time O (Mn^ + 1 2 +Mn^ + (4- ) ) and query time O (n^ 1- ). Here
@cite_3: 
@cite_27: We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic @math -approximate integral matching algorithm with small polylog worst-case update time. For the @math -approximation regime only a fractional fully-dynamic @math -matching algorithm with worst-case polylog update time was previously known, due to (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio.
@cite_50: We consider dynamic algorithms for maintaining Single-Source Reachability (SSR) and approximate Single-Source Shortest Paths (SSSP) on n-node m-edge directed graphs under edge deletions (decremental algorithms). The previous fastest algorithm for SSR and SSSP goes back three decades to Even and Shiloach (JACM 1981); it has O(1) query time and O(mn) total update time (i.e., linear amortized update time if all edges are deleted). This algorithm serves as a building block for several other dynamic algorithms. The question whether its total update time can be improved is a major, long standing, open problem. In this paper, we answer this question affirmatively. We obtain a randomized algorithm which, in a simplified form, achieves an O(mn0.984) expected total update time for SSR and (1 + e)-approximate SSSP, where O(·) hides poly log n. We also extend our algorithm to achieve roughly the same running time for Strongly Connected Components (SCC), improving the algorithm of Roditty and Zwick (FOCS 2002), and an algorithm that improves the O (mn log W)-time algorithm of Bernstein (STOC 2013) for approximating SSSP on weighted directed graphs, where the edge weights are integers from 1 to W. All our algorithms have constant query time in the worst case.
@cite_2: Recently we presented the first algorithm for maintaining the set of nodes reachable from a source node in a directed graph that is modified by edge deletions with (o(mn) ) total update time, where (m ) is the number of edges and (n ) is the number of nodes in the graph [ STOC 2014]. The algorithm is a combination of several different algorithms, each for a different (m ) vs. (n ) trade-off. For the case of (m = (n^ 1.5 ) ) the running time is (O(n^ 2.47 ) ), just barely below (mn = (n^ 2.5 ) ). In this paper we simplify the previous algorithm using new algorithmic ideas and achieve an improved running time of ( O ( ( m^ 7 6 n^ 2 3 , m^ 3 4 n^ 5 4 + o(1) , m^ 2 3 n^ 4 3+o(1) + m^ 3 7 n^ 12 7+o(1) )) ). This gives, e.g., (O(n^ 2.36 ) ) for the notorious case (m = (n^ 1.5 ) ). We obtain the same upper bounds for the problem of maintaining the strongly connected components of a directed graph undergoing edge deletions. Our algorithms are correct with high probabililty against an oblivious adversary.
@cite_31: In this paper we consider the decremental single-source shortest paths (SSSP) problem, where given a graph G and a source node s the goal is to maintain shortest paths between s and all other nodes in G under a sequence of online adversarial edge deletions. In their seminal work, Even and Shiloach [JACM 1981] presented an exact solution to the problem with only O(mn) total update time over all edge deletions. Their classic algorithm was the best known result for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. The first improvement over the Even-Shiloach algorithm was given by Bernstein and Roditty [SODA 2011], who for the case of an unweighted and undirected graph presented an approximate (1+) algorithm with constant query time and a total update time of O(n2+O(1 √logn)). This work triggered a series of new results, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a -approximate algorithm whose total update time is near linear O(m1+ O(1 √logn)). In this paper they posed as a major open problem the question of derandomizing their result. In fact, all known improvements over the Even-Shiloach algorithm are randomized. All these algorithms maintain some truncated shortest path trees from a small subset of nodes. While in the randomized setting it is possible to “hide” these nodes from the adversary, in the deterministic setting this is impossible: the adversary can delete all edges touching these nodes, thus forcing the algorithm to choose a new set of nodes and incur a new computation of shortest paths. In this paper we present the first deterministic decremental SSSP algorithm that breaks the Even-Shiloach bound of O(mn) total update time, for unweighted and undirected graphs. Our algorithm is (1 + є) approximate and achieves a total update time of O(n2). Our algorithm can also achieve the same bounds in the incremental setting. It is worth mentioning that for dense instances where m = Ω(n2 − 1 √log(n)), our algorithm is also faster than all existing randomized algorithms.
@cite_17: The decremental single-source shortest paths (SSSP) problem concerns maintaining the distances between a given source node s to every node in an n-node m-edge graph G undergoing edge deletions. While its static counterpart can be easily solved in near-linear time, this decremental problem is much more challenging even in the undirected unweighted case. In this case, the classic O(mn) total update time of Even and Shiloach (JACM 1981) has been the fastest known algorithm for three decades. With the loss of a (1 + aepsi;)-approximation factor, the running time was recently improved to O(n2+o(1)) by Bernstein and Roditty (SODA 2011), and more recently to O(n1.8+o(1) + m1+o(1)) by Henzinger, Krinninger, and Nanongkai (SODA 2014). In this paper, we finally bring the running time of this case down to near-linear: We give a (1 + aepsi;)-approximation algorithm with O(m1+o(1)) total update time, thus obtaining near-linear time. Moreover, we obtain O(m1+o(1)log W) time for the weighted case, where the edge weights are integers from 1 to W. The only prior work on weighted graphs in o(mn log W) time is the O(mn0.986 log W)-time algorithm by Henzinger, Krinninger, and Nanongkai (STOC 2014) which works for the general weighted directed case. In contrast to the previous results which rely on maintaining a sparse emulator, our algorithm relies on maintaining a so-called sparse (d, aepsi;)-hop set introduced by Cohen (JACM 2000) in the PRAM literature. A (d, aepsi;)-hop set of a graph G = (V, E) is a set E' of weighted edges such that the distance between any pair of nodes in G can be (1 + aepsi;)-approximated by their d-hop distance (given by a path containing at most d edges) on G'=(V, E a#x222A; E'). Our algorithm can maintain an (no(1), aepsi;)-hop set of near-linear size in near-linear time under edge deletions. It is the first of its kind to the best of our knowledge. To maintain the distances on this hop set, we develop a monotone bounded-hop Even-Shiloach tree. It results from extending and combining the monotone Even-Shiloach tree of Henzinger, Krinninger, and Nanongkai (FOCS 2013) with the bounded-hop SSSP technique of Bernstein (STOC 2013). These two new tools might be of independent interest.
In the deterministic regime no algorithm for the directed case is known that is asymptotically better (up to ploylog) than invoking APSP algorithm. Interestingly, in the fault-tolerant and the dynamic settings many of the existing algorithms are randomized, and for many of the problems there is a polynomial gap between the best randomized and deterministic algorithms (see e.g. sensitive distance oracles @cite_11 , dynamic shortest paths @cite_17 @cite_31 , dynamic strongly connected components @cite_50 @cite_2 @cite_30 , dynamic matching @cite_3 @cite_27 , and many more). Randomization is a powerful tool in the classic setting of graph algorithms with full knowledge and is often used to simplify the algorithm and to speed-up its running time. However, physical computers are deterministic machines, and obtaining true randomness can be a hard task to achieve. A central line of research is focused on the derandomization of algorithms that relies on randomness.