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.
The replacement paths problem. The replacement paths problem is motivated by several different applications and has been extensively studied in the last few decades (see e.g. @cite_6 @cite_13 @cite_8 @cite_46 @cite_45 @cite_33 @cite_10 @cite_39 @cite_20 @cite_21 ). It is well motivated by its own right from the fault-tolerance perspective. In many applications it is desired to find algorithms and data-structures that are resilient to failures. Since links in a network can fail, it is important to find backup shortest paths between important vertices of the graph.
@cite_33 @cite_8 @cite_10 @cite_21 @cite_6 @cite_39 @cite_45 @cite_46 @cite_13 @cite_20
2094099891 2621618541 2118681568 1998002108 2132422341 2028186501 2112582109 2019003829 2046236705 1975407578
Given a directed, non-negatively weighted graph G=(V,E) and s,t@?V, we consider two problems. In the k simple shortest paths problem, we want to find the k simple paths from s to t with the k smallest weights. In the replacement paths problem, we want the shortest path from s to t that avoids e, for every edge e in the original shortest path from s to t. The best known algorithm for the k simple shortest paths problem has a running of O(k(mn+n^2logn)). For the replacement paths problem the best known result is the trivial one running in time O(mn+n^2logn). In this paper we present two simple algorithms for the replacement paths problem and the k simple shortest paths problem in weighted directed graphs (using a solution of the All Pairs Shortest Paths problem). The running time of our algorithm for the replacement paths problem is O(mn+n^2loglogn). For the k simple shortest paths we will perform O(k) iterations of the second simple shortest path (each in O(mn+n^2loglogn) running time) using a useful property of Roditty and Zwick [L. Roditty, U. Zwick, Replacement paths and k simple shortest paths in unweighted directed graphs, in: Proc. of International Conference on Automata, Languages and Programming (ICALP), 2005, pp. 249-260]. These running times immediately improve the best known results for both problems over sparse graphs. Moreover, we prove that both the replacement paths and the k simple shortest paths (for constant k) problems are not harder than APSP (All Pairs Shortest Paths) in weighted directed graphs. Let G = (V(G), E(G)) be a weighted directed graph and let P be a shortest path from s to t in G. In the replacement paths problem we are required to compute for every edge e in P, the length of a shortest path from s to t that avoids e. The fastest known algorithm for solving the problem in weighted directed graphs is the trivial one: each edge in P is removed from the graph in its turn and the distance from s to t in the modified graph is computed. The running time of this algorithm is O (mn + n2 log n), where n = |V(G)| and m = |E(G)|. The replacement paths problem is strongly motivated by two different applications. First, the fastest algorithm to compute the k simple shortest paths from s to t in directed graphs [21, 13] repeatedly computes the replacement paths from s to t. Its running time is O(kn(m + n log n)). Second, the computation of Vickrey pricing of edges in distributed networks can be reduced to the replacement paths problem. An open question raised by Nisan and Ronen [16] asks whether it is possible to compute the Vickrey pricing faster than the trivial algorithm described in the previous paragraph. In this paper we present a near-linear time algorithm for computing replacement paths in weighted planar directed graphs. In particular, the algorithm computes the lengths of the replacement paths in O(n log3 n) time. This result immediately improves the running time of the two applications mentioned above by almost a linear factor. Our algorithm is obtained by combining several new ideas with a data structure of Klein [12] that supports multi-source shortest paths queries in planar directed graphs in logarithmic time. Our algorithm can be adapted to address the variant of the problem in which one is interested in the replacement path itself (rather than the length of the path). In that case the algorithm is executed in a preprocessing stage constructing a data structure that supports replacement path queries in time O(h), where h is the number of hops in the replacement path. In addition, we can handle the variant in which vertices should be avoided instead of edges. A naive algorithm for the replacement paths problem runs in O(n(m+n logn)) time, executing the single-source shortest path algorithm up to n times. In our paper [3], we claimed that the replacement paths problem can be solved inO(m+n logn) time for both undirected and directed graphs. However, there is a flaw that invalidates the algorithm for directed graphs. (The algorithm for undirected graphs remains valid.) The same bound for undirected graphs is also achieved by Nardelli, Proietti, and Widmayer [6], who solve the most vital node problem with an algorithm that also solves the replacement paths problem. Their work is in turn based on earlier work by Malik, Mittal and Gupta [5], Ball, Golden, and Vohra [1] and BarNoy, Khuller, and Schieber [2]. The error in our algorithm for directed graphs led us to investigate the hardness of the replacement paths problem and other related problems. We have recently established lower bounds that show that no replacement paths algorithm of a certain class (including all known algorithms) can achieve the running time of the algorithm for undirected graphs [4]. The mistake in the directed graph algorithm of [3] occurs on page 257, just after Lemma 2, where we say “A simple corollary of this lemma is the fact that if (u; v) is the single edge of path(x; y; G n e) in E(Vx; Vy), then Let G = (V, E) be a directed graph with positive edge weights, let s, t be two specified vertices in this graph, and let π(s, t) be the shortest path between them. In the replacement paths problem we want to compute, for every edge e on π(s, t), the shortest path from s to t that avoids e. The naive solution to this problem would be to remove each edge e, one at a time, and compute the shortest s - t path each time; this yields a running time of O(mn + n2 log n). Gotthilf and Lewenstein [8] recently improved this to O(mn+n2 log log n), but no o(mn) algorithms are known. We present the first approximation algorithm for replacement paths in directed graphs with positive edge weights. Given any e e [0, 1), our algorithm returns (1 + e)-approximate replacement paths in O(e-1 log2 n log(nC c)(m+n log n)) = O(m log(nC c) e) time, where C is the largest edge weight in the graph and c is the smallest weight. We also present an even faster (1 + e) approximate algorithm for the simpler problem of approximating the k shortest simple s - t paths in a directed graph with positive edge weights. That is, our algorithm outputs k different simple s - t paths, where the kth path we output is a (1 + e) approximation to the actual kth shortest simple s - t path. The running time of our algorithm is O(ke-1 log2 n(m + n log n)) = O(km e). The fastest exact algorithm for this problem has a running time of O(k(mn+n2 log log n)) = O(kmn) [8]. The previous best approximation algorithm was developed by Roditty [15]; it has a stretch of 3 2 and a running time of O(km√n) (it does not work for replacement paths). Note that all of our running times are nearly optimal except for the O (log(nC c)) factor in the replacements paths algorithm. Also, our algorithm can solve the variant of approximate replacement paths where we avoid vertices instead of edges. We investigate the single link failure recovery problem and its application to the alternate path routing problem for ATM networks, and the k-replacement edges for each edge of a minimum cost spanning tree. Specifically, given a 2-connected graph G, a specified node s, and a shortest paths tree Ts = e1, e2, . . . , eni1 of s, where ei = (xi, yi) and xi = parentTs(yi), find a shortest path from yi to s in the graph G for 1 · i · n i 1. We present an O(m + n log n) time algorithm for this problem and a linear time algorithm for the case when all weights are equal. When the edge weights are integers, we present an algorithm that takes O(m + Tsort(n)) time, where Tsort(n) is the time required to sort n integers. We establish a lower bound of ­(min(m p n, n 2 )) for the directed version of our problem under the path comparison model, where Ts is the shortest paths destination tree of s. We show that any solution to the single link recovery problem can be adapted to solve the alternate path routing problem in ATM networks. Our technique for the single link failure recovery problem is adapted to find the k-replacement edges for the tree edges of a minimum cost spanning tree in O(m + n log n) time. Abstract The shortest path problem is of great importance to the real world in such areas as transportation, network design, telecommunication, etc. The deterministic version of the problem is easily solved. However, in the real world, uncertainty is frequently encountered and must be dealt with. For instance, in a transportation network, the path that has the least travel time when no traffic is present might be prone to accidents and traffic jams, and thus it may lead to a drastic increase in travel time during rush hours. In situations with significant uncertainty, the deterministic approach can be far from sufficient. New and appropriate criteria and models to handle uncertainties along with efficient solution techniques are in need. In this paper, we take a minimax approach to measure the performance under uncertainties. Under our measure, one path is superior to all others only if its worst case performance is better than that of the others. The complexity of the defined models, exact and heuristic solution methods are explored and presented. Analysis is done to examine the performance of the heuristic method. The shortest path (SP) problem in a network with nonnegative arc lengths can be solved easily by Dijkstra's labeling algorithm in polynomial time. In the case of significant uncertainty of the arc lengths, a robustness approach is more appropriate. In this paper, we study the SP problem under arc length uncertainties. A scenario approach is adopted to characterize uncertainties. Two robustness criteria are specified: the absolute robust criterion and the robust deviation criterion. We show that under both criteria the robust SP problem is NP-complete even for the much more restricted layered networks of width 2, and with only 2 scenarios. A pseudo-polynomial algorithm is devised to solve the robust SP problem in general networks under bounded number of scenarios. Also presented is a more efficient algorithm for layered networks. However, in the case of unlimited number of scenarios, we show that the robust SP problem is strongly NP-hard. A simple heuristic for finding a good robust shortest path is provided, and the worst case performance is analyzed. We study a new robust path problem, the Online Replacement Path problem (ORP). Consider the problem of routing a physical package through a faulty network G = (V,E) from a source s ∈ V to a destination t ∈ V as quickly as possible. An adversary, whose objective is to maximize the latter routing time, can choose to remove a single edge in the network. In one setup, the identity of the edge is revealed to the routing mechanism (RM) while the package is in s. In this setup the best strategy is to route the package along the shortest path in the remaining network. The payoff maximization problem for the adversary becomes the Most Vital Arc problem (MVA), which amounts to choosing the edge in the network whose removal results in a maximal increase of the s-t distance. However, the assumption that the RM is informed about the failed edge when standing at s is unrealistic in many applications, in which failures occur online, and, in particular, after the routing has started. We therefore consider the setup in which the adversary can reveal the identity of the failed edge just before the RM attempts to use this edge, thus forcing it to use a different route to t, starting from the current node. The problem of choosing the nominal path minimizing the worst case arrival time at t in this setup is ORP. We show that ORP can be solved in polynomial time and study other models naturally providing middle grounds between MVA and ORP. Our results show that ORP comprises a highly flexible and tractable framework for dealing with robustness issues in the design of RM-s. We consider the point-to-point (approximate) shortest-path query problem, which is the following generalization of the classical single-source (SSSP) and all-pairs shortest-path (APSP) problems: we are first presented with a network (graph). A so-called preprocessing algorithm may compute certain information (a data structure or index) to prepare for the next phase. After this preprocessing step, applications may ask shortest-path or distance queries, which should be answered as fast as possible. Due to its many applications in areas such as transportation, networking, and social science, this problem has been considered by researchers from various communities (sometimes under different names): algorithm engineers construct fast route planning methods; database and information systems researchers investigate materialization tradeoffs, query processing on spatial networks, and reachability queries; and theoretical computer scientists analyze distance oracles and sparse spanners. Related problems are considered for compact routing and distance labeling schemes in networking and distributed computing and for metric embeddings in geometry as well. In this survey, we review selected approaches, algorithms, and results on shortest-path queries from these fields, with the main focus lying on the tradeoff between the index size and the query time. We survey methods for general graphs as well as specialized methods for restricted graph classes, in particular for those classes with arguable practical significance such as planar graphs and complex networks. This paper studies the problem of finding a priori shortest paths to guarantee a given likelihood of arriving on-time in a stochastic network. Such "reliable" paths help travelers better plan their trips to prepare for the risk of running late in the face of stochastic travel times. Optimal solutions to the problem can be obtained from local-reliable paths, which are a set of non-dominated paths under first-order stochastic dominance. We show that Bellman's principle of optimality can be applied to construct local-reliable paths. Acyclicity of local-reliable paths is established and used for proving finite convergence of solution procedures. The connection between the a priori path problem and the corresponding adaptive routing problem is also revealed. A label-correcting algorithm is proposed and its complexity is analyzed. A pseudo-polynomial approximation is proposed based on extreme-dominance. An extension that allows travel time distribution functions to vary over time is also discussed. We show that the time-dependent problem is decomposable with respect to arrival times and therefore can be solved as easily as its static counterpart. Numerical results are provided using typical transportation networks. The classic all-terminal network reliability problem posits a graph, each of whose edges fails independently with some given probability. The goal is to determine the probability that the network becomes disconnected due to edge failures. This problem has obvious applications in the design of communication networks. Since the problem is @math -complete and thus believed hard to solve exactly, a great deal of research has been devoted to estimating the failure probability. In this paper, we give a fully polynomial randomized approximation scheme that, given any n-vertex graph with specified failure probabilities, computes in time polynomial in n and @math an estimate for the failure probability that is accurate to within a relative error of @math with high probability. We also give a deterministic polynomial approximation scheme for the case of small failure probabilities. Some extensions to evaluating probabilities of @math -connectivity, strong connectivity in directed Eulerian graphs and @math -way disconnection, and to evaluating the Tutte polynomial are also described. This version of the paper corrects several errata that appeared in the previous journal publication [D. R. Karger, SIAM J. Comput., 29 (1999), pp. 492--514].