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.
The optimization problem is considerably harder. A version of the problem, called DPP, where the each of the path need to have length bounded by some integer @math . This problem is -hard in the strong sense even in the One-face case for non-fixed @math @cite_29 . For the shortest @math -DPP, where we want to minimise the sum of the lengths of the paths, very few instances are known to be solvable in polynomial time. For general undirected graphs, very recently, Bj " o rklund and Husfeldt @cite_2 have shown that shortest @math -DPP admits a randomised polynomial time algorithm. The deterministic polynomial time bound for the same – to this date – remains an intriguing open question.
@cite_29 @cite_2
2021673830 65356316
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. In the distributed all-pairs shortest paths problem (APSP), every node in the weighted undirected distributed network (the CONGEST model) needs to know the distance from every other node using least number of communication rounds (typically called time complexity ). The problem admits @math -approximation @math -time algorithm and a nearly-tight @math lower bound [Nanongkai, STOC'14; Lenzen and Patt-Shamir PODC'15] @math , @math and @math hide polylogarithmic factors. Note that the lower bounds also hold even in the unweighted case and in the weighted case with polynomial approximation ratios LenzenP_podc13,HolzerW12,PelegRT12,Nanongkai-STOC14 . . For the exact case, Elkin [STOC'17] presented an @math time bound, which was later improved to @math [Huang, Nanongkai, Saranurak FOCS'17]. It was shown that any super-linear lower bound (in @math ) requires a new technique [Censor-Hillel, Khoury, Paz, DISC'17], but otherwise it remained widely open whether there exists a @math -time algorithm for the exact case, which would match the best possible approximation algorithm. This paper resolves this question positively: we present a randomized (Las Vegas) @math -time algorithm, matching the lower bound up to polylogarithmic factors. Like the previous @math bound, our result works for directed graphs with zero (and even negative) edge weights. In addition to the improved running time, our algorithm works in a more general setting than that required by the previous @math bound; in our setting (i) the communication is only along edge directions (as opposed to bidirectional), and (ii) edge weights are arbitrary (as opposed to integers in 1, 2, ... poly(n) ). ... We present a method for solving the shortest transshipmen problem - also known as uncapacitated minimum cost flow - up to a multiplicative error of @math in undirected graphs with polynomially bounded integer edge weights using a tailored gradient descent algorithm. An important special case of the transshipment problem is the single-source shortest paths (SSSP) problem. Our gradient descent algorithm takes @math iterations, and in each iteration it needs to solve the transshipment problem up to a multiplicative error of @math , where @math is the number of nodes. In particular, this allows us to perform a single iteration by computing a solution on a sparse spanner of logarithmic stretch. As a consequence, we improve prior work by obtaining the following results: (1) Broadcast congest model: @math -approximate SSSP using @math rounds, where @math is the (hop) diameter of the network. (2) Broadcast congested clique model: @math -approximate transshipment and SSSP using @math rounds. (3) Multipass streaming model: @math -approximate transshipment and SSSP using @math space and @math passes. The previously fastest algorithms for these models leverage sparse hop sets. We bypass the hop set construction; computing a spanner is sufficient with our method. The above bounds assume non-negative integer edge weights that are polynomially bounded in @math ; for general non-negative weights, running times scale with the logarithm of the maximum ratio between non-zero weights. In case of asymmetric costs, running times scale with the maximum ratio between the costs of both directions over all edges. We obtain the following results related to dynamic versions of the shortest-paths problem: Reductions that show that the incremental and decremental single-source shortest-paths problems, for weighted directed or undirected graphs, are, in a strong sense, at least as hard as the static all-pairs shortest-paths problem. We also obtain slightly weaker results for the corresponding unweighted problems. A randomized fully-dynamic algorithm for the all-pairs shortest-paths problem in directed unweighted graphs with an amortized update time of @math (we use @math to hide small poly-logarithmic factors) and a worst case query time is O(n3 4). A deterministic O(n2log n) time algorithm for constructing an O(log n)-spanner with O(n) edges for any weighted undirected graph on n vertices. The algorithm uses a simple algorithm for incrementally maintaining single-source shortest-paths tree up to a given distance.