We study a natural online variant of the replacement path problem. The asks to find for a given graph @math , two designated vertices @math and a shortest @math - @math path @math in @math , a @math for every edge @math on the path @math . The replacement path @math is simply a shortest @math - @math path in the graph, which avoids the edge @math . We adapt this problem to deal with the natural scenario, that the edge which failed is not known at the time of solution implementation. Instead, our problem assumes that the identity of the failed edge only becomes available when the routing mechanism tries to cross the edge. This situation is motivated by applications in distributed networks, where information about recent changes in the network is only stored locally, and fault-tolerant optimization, where an adversary tries to delay the discovery of the materialized scenario as much as possible. Consequently, we define the , which asks to find a nominal @math - @math path @math and detours @math for every edge on the path @math , such that the worst-case arrival time at the destination is minimized. Our main contribution is a label setting algorithm, which solves the problem in undirected graphs in time @math and linear space for all sources and a single destination. We also present algorithms for extensions of the model to any bounded number of failed edges.
The complexity of the RP problem for undirected graphs is well understood. Malik, Mittal and Gupta @cite_17 give a simple @math algorithm. A mistake in this paper was later corrected by Bar-Noy, Khuller and Schieber @cite_7 . This running time is asymptotically the same as a single source shortest path computation. Nardelli, Proietti and Widmayer @cite_10 later provided an algorithm with the same complexity for the variant of RP, in which vertices are removed instead of edges. The same authors give efficient algorithms for finding detour-critical edges for a given shortest path in @cite_20 @cite_23 .
@cite_7 @cite_23 @cite_10 @cite_20 @cite_17
2118681568 2151239055 2418286382 2787728049
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 Given an arc-weighted directed graph G = (V, A, spl lscr ) and a pair of nodes s, t, we seek to find an s-t walk of length at most B that maximizes some given function f of the set of nodes visited by the walk. The simplest case is when we seek to maximize the number of nodes visited: this is called the orienteering problem. Our main result is a quasi-polynomial time algorithm that yields an O(log OPT) approximation for this problem when f is a given submodular set function. We then extend it to the case when a node v is counted as visited only if the walk reaches v in its time window [R(v), D(v)]. We apply the algorithm to obtain several new results. First, we obtain an O(log OPT) approximation for a generalization of the orienteering problem in which the profit for visiting each node may vary arbitrarily with time. This captures the time window problem considered earlier for which, even in undirected graphs, the best approximation ratio known [Bansal, (2004)] is O(log sup 2 OPT). The second application is an O(log sup 2 k) approximation for the k-TSP problem in directed graphs (satisfying asymmetric triangle inequality). This is the first non-trivial approximation algorithm for this problem. The third application is an O(log sup 2 k) approximation (in quasi-poly time) for the group Steiner problem in undirected graphs where k is the number of groups. This improves earlier ratios (Garg, ) by a logarithmic factor and almost matches the inapproximability threshold on trees (Halperin and Krauthgamer, 2003). This connection to group Steiner trees also enables us to prove that the problem we consider is hard to approximate to a ratio better than spl Omega (log sup 1- spl epsi OPT), even in undirected graphs. Even though our algorithm runs in quasi-poly time, we believe that the implications for the approximability of several basic optimization problems are interesting. 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. The well-known @math -disjoint path problem ( @math -DPP) asks for pairwise vertex-disjoint paths between @math specified pairs of vertices @math in a given graph, if they exist. The decision version of the shortest @math -DPP asks for the length of the shortest (in terms of total length) such paths. Similarly the search and counting versions ask for one such and the number of such shortest set of paths, respectively. We restrict attention to the shortest @math -DPP instances on undirected planar graphs where all sources and sinks lie on a single face or on a pair of faces. We provide efficient sequential and parallel algorithms for the search versions of the problem answering one of the main open questions raised by Colin de Verdiere and Schrijver for the general one-face problem. We do so by providing a randomised @math algorithm along with an @math time randomised sequential algorithm. We also obtain deterministic algorithms with similar resource bounds for the counting and search versions. In contrast, previously, only the sequential complexity of decision and search versions of the "well-ordered" case has been studied. For the one-face case, sequential versions of our routines have better running times for constantly many terminals. In addition, the earlier best known sequential algorithms (e.g. ) were randomised while ours are also deterministic. The algorithms are based on a bijection between a shortest @math -tuple of disjoint paths in the given graph and cycle covers in a related digraph. This allows us to non-trivially modify established techniques relating counting cycle covers to the determinant. We further need to do a controlled inclusion-exclusion to produce a polynomial sum of determinants such that all "bad" cycle covers cancel out in the sum allowing us to count "good" cycle covers.