Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecremental SSSP in Weighted Digraphs: Faster and Against an Adaptive Adversary
220
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
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.
rate research
Read More
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.
Given a directed graph $G = (V,E)$, undergoing an online sequence of edge deletions with $m$ edges in the initial version of $G$ and $n = |V|$, we consider the problem of maintaining all-pairs shortest paths (APSP) in $G$. Whilst this problem has been studied in a long line of research [ACM81, FOCS99, FOCS01, STOC02, STOC03, SWAT04, STOC13] and the problem of $(1+epsilon)$-approximate, weighted APSP was solved to near-optimal update time $tilde{O}(mn)$ by Bernstein [STOC13], the problem has mainly been studied in the context of oblivious adversaries, which assumes that the adversary fixes the update sequence before the algorithm is started. In this paper, we make significant progress on the problem in the setting where the adversary is adaptive, i.e. can base the update sequence on the output of the data structure queries. We present three new data structures that fit different settings: We first present a deterministic data structure that maintains exact distances with total update time $tilde{O}(n^3)$. We also present a deterministic data structure that maintains $(1+epsilon)$-approximate distance estimates with total update time $tilde O(sqrt{m} n^2/epsilon)$ which for sparse graphs is $tilde O(n^{2+1/2}/epsilon)$. Finally, we present a randomized $(1+epsilon)$-approximate data structure which works against an adaptive adversary; its total update time is $tilde O(m^{2/3}n^{5/3} + n^{8/3}/(m^{1/3}epsilon^2))$ which for sparse graphs is $tilde O(n^{2+1/3})$. Our exact data structure matches the total update time of the best randomized data structure by Baswana et al. [STOC02] and maintains the distance matrix in near-optimal time. Our approximate data structures improve upon the best data structures against an adaptive adversary which have $tilde{O}(mn^2)$ total update time [JACM81, STOC03].
We present a new dynamic matching sparsification scheme. From this scheme we derive a framework for dynamically rounding fractional matchings against emph{adaptive adversaries}. Plugging in known dynamic fractional matching algorithms into our framework, we obtain numerous randomized dynamic matching algorithms which work against adaptive adversaries (the first such algorithms, as all previous randomized algorithms for this problem assumed an emph{oblivious} adversary). In particular, for any constant $epsilon>0$, our framework yields $(2+epsilon)$-approximate algorithms with constant update time or polylog worst-case update time, as well as $(2-delta)$-approximate algorithms in bipartite graphs with arbitrarily-small polynomial update time, with all these algorithms guarantees holding against adaptive adversaries. All these results achieve emph{polynomially} better update time to approximation tradeoffs than previously known to be achievable against adaptive adversaries.
Designing dynamic graph algorithms against an adaptive adversary is a major goal in the field of dynamic graph algorithms. While a few such algorithms are known for spanning trees, matchings, and single-source shortest paths, very little was known for an important primitive like graph sparsifiers. The challenge is how to approximately preserve so much information about the graph (e.g., all-pairs distances and all cuts) without revealing the algorithms underlying randomness to the adaptive adversary. In this paper we present the first non-trivial efficient adaptive algorithms for maintaining spanners and cut sparisifers. These algorithms in turn imply improvements over existing algorithms for other problems. Our first algorithm maintains a polylog$(n)$-spanner of size $tilde O(n)$ in polylog$(n)$ amortized update time. The second algorithm maintains an $O(k)$-approximate cut sparsifier of size $tilde O(n)$ in $tilde O(n^{1/k})$ amortized update time, for any $kge1$, which is polylog$(n)$ time when $k=log(n)$. The third algorithm maintains a polylog$(n)$-approximate spectral sparsifier in polylog$(n)$ amortized update time. The amortized update time of both algorithms can be made worst-case by paying some sub-polynomial factors. Prior to our result, there were near-optimal algorithms against oblivious adversaries (e.g. Baswana et al. [TALG12] and Abraham et al. [FOCS16]), but the only non-trivial adaptive dynamic algorithm requires $O(n)$ amortized update time to maintain $3$- and $5$-spanner of size $O(n^{1+1/2})$ and $O(n^{1+1/3})$, respectively [Ausiello et al. ESA05]. Our results are based on two novel techniques. The first technique, is a generic black-box reduction that allows us to assume that the graph undergoes only edge deletions and, more importantly, remains an expander with almost-uniform degree. The second technique we call proactive resampling. [...]
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
