Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNear-Optimal Decremental SSSP in Dense Weighted Digraphs
363
0
0.0
(
0
)
Added by
Maximilian Probst Gutenberg
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
In the decremental Single-Source Shortest Path problem (SSSP), we are given a weighted directed graph $G=(V,E,w)$ undergoing edge deletions and a source vertex $r in V$; let $n = |V|, m = |E|$ and $W$ be the aspect ratio of the graph. The goal is to obtain a data structure that maintains shortest paths from $r$ to all vertices in $V$ and can answer distance queries in $O(1)$ time, as well as return the corresponding path $P$ in $O(|P|)$ time. This problem was first considered by Even and Shiloach [JACM81], who provided an algorithm with total update time $O(mn)$ for unweighted undirected graphs; this was later extended to directed weighted graphs [FOCS95, STOC99]. There are conditional lower bounds showing that $O(mn)$ is in fact near-optimal [ESA04, FOCS14, STOC15, STOC20]. In a breakthrough result, Forster et al. showed that it is possible to achieve total update time $mn^{0.9+o(1)}log W$ if the algorithm is allowed to return $(1+{epsilon})$-approximate paths, instead of exact ones [STOC14, ICALP15]. No further progress was made until Probst Gutenberg and Wulff-Nilsen [SODA20] provided a new approach for the problem, which yields total time $tilde{O}(min{m^{2/3}n^{4/3}log W, (mn)^{7/8} log W})$. Our result builds on this recent approach, but overcomes its limitations by introducing a significantly more powerful abstraction, as well as a different core subroutine. Our new framework yields a decremental $(1+{epsilon})$-approximate SSSP data structure with total update time $tilde{O}(n^2 log^4 W)$. Our algorithm is thus near-optimal for dense graphs with polynomial edge-weights. Our framework can also be applied to sparse graphs to obtain total update time $tilde{O}(mn^{2/3} log^3 W)$. Our main technique allows us to convert SSSP algorithms for DAGs to ones for general graphs, which we believe has significant potential to influence future work.
rate research
Read More
Given a dynamic digraph $G = (V,E)$ undergoing edge deletions and given $sin V$ and $epsilon>0$, we consider the problem of maintaining $(1+epsilon)$-approximate shortest path distances from $s$ to all vertices in $G$ over the sequence of deletions. Even and Shiloach (J.~ACM$81$) give a deterministic data structure for the exact version of the problem with total update time $O(mn)$. Henzinger et al. (STOC$14$, ICALP$15$) give a Monte Carlo data structure for the approximate version with improved total update time $ O(mn^{0.9 + o(1)}log W)$ where $W$ is the ratio between the largest and smallest edge weight. A drawback of their data structure is that they only work against an oblivious adversary, meaning that the sequence of deletions needs to be fixed in advance. This limits its application as a black box inside algorithms. We present the following $(1+epsilon)$-approximate data structures: (1) the first data structure is Las Vegas and works against an adaptive adversary; it has total expected update time $tilde O(m^{2/3}n^{4/3})$ for unweighted graphs and $tilde O(m^{3/4}n^{5/4}log W)$ for weighted graphs, (2) the second data structure is Las Vegas and assumes an oblivious adversary; it has total expected update time $tilde O(sqrt m n^{3/2})$ for unweighted graphs and $tilde O(m^{2/3}n^{4/3}log W)$ for weighted graphs, (3) the third data structure is Monte Carlo and is correct w.h.p.~against an oblivious adversary; it has total expected update time $tilde O((mn)^{7/8}log W) = tilde O(mn^{3/4}log W)$. Each of our data structures can be queried at any stage of $G$ in constant worst-case time; if the adversary is oblivious, a query can be extended to also report such a path in time proportional to its length. Our update times are faster than those of Henzinger et al.~for all graph densities.
Given a weighted undirected graph $G=(V,E,w)$, a hopset $H$ of hopbound $beta$ and stretch $(1+epsilon)$ is a set of edges such that for any pair of nodes $u, v in V$, there is a path in $G cup H$ of at most $beta$ hops, whose length is within a $(1+epsilon)$ factor from the distance between $u$ and $v$ in $G$. We show the first efficient decremental algorithm for maintaining hopsets with a polylogarithmic hopbound. The update time of our algorithm matches the best known static algorithm up to polylogarithmic factors. All the previous decremental hopset constructions had a superpolylogarithmic (but subpolynomial) hopbound of $2^{log^{Omega(1)} n}$ [Bernstein, FOCS09; HKN, FOCS14; Chechik, FOCS18]. By applying our decremental hopset construction, we get improved or near optimal bounds for several distance problems. Most importantly, we show how to decrementally maintain $(2k-1)(1+epsilon)$-approximate all-pairs shortest paths (for any constant $k geq 2)$, in $tilde{O}(n^{1/k})$ amortized update time and $O(k)$ query time. This significantly improves (by a polynomial factor) over the update-time of the best previously known decremental algorithm in the constant query time regime. Moreover, it improves over the result of [Chechik, FOCS18] that has a query time of $O(log log(nW))$, where $W$ is the aspect ratio, and the amortized update time is $n^{1/k}cdot(frac{1}{epsilon})^{tilde{O}(sqrt{log n})}$. For sparse graphs our construction nearly matches the best known static running time/ query time tradeoff.
In the decremental single-source shortest paths problem, the goal is to maintain distances from a fixed source $s$ to every vertex $v$ in an $m$-edge graph undergoing edge deletions. In this paper, we conclude a long line of research on this problem by showing a near-optimal deterministic data structure that maintains $(1+epsilon)$-approximate distance estimates and runs in $m^{1+o(1)}$ total update time. Our result, in particular, removes the oblivious adversary assumption required by the previous breakthrough result by Henzinger et al. [FOCS14], which leads to our second result: the first almost-linear time algorithm for $(1-epsilon)$-approximate min-cost flow in undirected graphs where capacities and costs can be taken over edges and vertices. Previously, algorithms for max flow with vertex capacities, or min-cost flow with any capacities required super-linear time. Our result essentially completes the picture for approximate flow in undirected graphs. The key technique of the first result is a novel framework that allows us to treat low-diameter graphs like expanders. This allows us to harness expander properties while bypassing shortcomings of expander decomposition, which almost all previous expander-based algorithms needed to deal with. For the second result, we break the notorious flow-decomposition barrier from the multiplicative-weight-update framework using randomization.
In this thesis, we present new techniques to deal with fundamental algorithmic graph problems where graphs are directed and partially dynamic, i.e. undergo either a sequence of edge insertions or deletions: - Single-Source Reachability (SSR), - Strongly-Connected Components (SCCs), and - Single-Source Shortest Paths (SSSP). These problems have recently received an extraordinary amount of attention due to their role as subproblems in various more complex and notoriously hard graph problems, especially to compute flows, bipartite matchings and cuts. Our techniques lead to the first near-optimal data structures for these problems in various different settings. Letting $n$ denote the number of vertices in the graph and by $m$ the maximum number of edges in any version of the graph, we obtain - the first randomized data structure to maintain SSR and SCCs in near-optimal total update time $tilde{O}(m)$ in a graph undergoing edge deletions. - the first randomized data structure to maintain SSSP in partially dynamic graphs in total update time $tilde{O}(n^2)$ which is near-optimal in dense graphs. - the first deterministic data structures for SSR and SCC for graphs undergoing edge deletions, and for SSSP in partially dynamic graphs that improve upon the $O(mn)$ total update time by Even and Shiloach from 1981 that is often considered to be a fundamental barrier.
We study the decremental All-Pairs Shortest Paths (APSP) problem in undirected edge-weighted graphs. The input to the problem is an $n$-vertex $m$-edge graph $G$ with non-negative edge lengths, that undergoes a sequence of edge deletions. The goal is to support approximate shortest-path queries: given a pair $x,y$ of vertices of $G$, return a path $P$ connecting $x$ to $y$, whose length is within factor $alpha$ of the length of the shortest $x$-$y$ path, in time $tilde O(|E(P)|)$, where $alpha$ is the approximation factor of the algorithm. APSP is one of the most basic and extensively studied dynamic graph problems. A long line of work culminated in the algorithm of [Chechik, FOCS 2018] with near optimal guarantees for the oblivious-adversary setting. Unfortunately, adaptive-adversary setting is still poorly understood. For unweighted graphs, the algorithm of [Henzinger, Krinninger and Nanongkai, FOCS 13, SICOMP 16] achieves a $(1+epsilon)$-approximation with total update time $tilde O(mn/epsilon)$; the best current total update time of $n^{2.5+O(epsilon)}$ is achieved by the deterministic algorithm of [Chuzhoy, Saranurak, SODA21], with $2^{O(1/epsilon)}$-multiplicative and $2^{O(log^{3/4}n/epsilon)}$-additive approximation. To the best of our knowledge, for arbitrary non-negative edge weights, the fastest current adaptive-update algorithm has total update time $O(n^{3}log L/epsilon)$, achieving a $(1+epsilon)$-approximation. Here, L is the ratio of longest to shortest edge lengths. Our main result is a deterministic algorithm for decremental APSP in undirected edge-weighted graphs, that, for any $Omega(1/loglog m)leq epsilon< 1$, achieves approximation factor $(log m)^{2^{O(1/epsilon)}}$, with total update time $Oleft (m^{1+O(epsilon)}cdot (log m)^{O(1/epsilon^2)}cdot log Lright )$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
