Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDeterministic Decremental Reachability, SCC, and Shortest Paths via Directed Expanders and Congestion Balancing
206
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
Let $G = (V,E,w)$ be a weighted, digraph subject to a sequence of adversarial edge deletions. In the decremental single-source reachability problem (SSR), we are given a fixed source $s$ and the goal is to maintain a data structure that can answer path-queries $s rightarrowtail v$ for any $v in V$. In the more general single-source shortest paths (SSSP) problem the goal is to return an approximate shortest path to $v$, and in the SCC problem the goal is to maintain strongly connected components of $G$ and to answer path queries within each component. All of these problems have been very actively studied over the past two decades, but all the fast algorithms are randomized and, more significantly, they can only answer path queries if they assume a weaker model: they assume an oblivious adversary which is not adaptive and must fix the update sequence in advance. This assumption significantly limits the use of these data structures, most notably preventing them from being used as subroutines in static algorithms. All the above problems are notoriously difficult in the adaptive setting. In fact, the state-of-the-art is still the Even and Shiloach tree, which dates back all the way to 1981 and achieves total update time $O(mn)$. We present the first algorithms to break through this barrier: 1) deterministic decremental SSR/SCC with total update time $mn^{2/3 + o(1)}$ 2) deterministic decremental SSSP with total update time $n^{2+2/3+o(1)}$. To achieve these results, we develop two general techniques of broader interest for working with dynamic graphs: 1) a generalization of expander-based tools to dynamic directed graphs, and 2) a technique that we call congestion balancing and which provides a new method for maintaining flow under adversarial deletions. Using the second technique, we provide the first near-optimal algorithm for decremental bipartite matching.
rate research
Read More
In the decremental single-source shortest paths (SSSP) problem, the input is an undirected graph $G=(V,E)$ with $n$ vertices and $m$ edges undergoing edge deletions, together with a fixed source vertex $sin V$. The goal is to maintain a data structure that supports shortest-path queries: given a vertex $vin V$, quickly return an (approximate) shortest path from $s$ to $v$. The decremental all-pairs shortest paths (APSP) problem is defined similarly, but now the shortest-path queries are allowed between any pair of vertices of $V$. Both problems have been studied extensively since the 80s, and algorithms with near-optimal total update time and query time have been discovered for them. Unfortunately, all these algorithms are randomized and, more importantly, they need to assume an oblivious adversary. Our first result is a deterministic algorithm for the decremental SSSP problem on weighted graphs with $O(n^{2+o(1)})$ total update time, that supports $(1+epsilon)$-approximate shortest-path queries, with query time $O(|P|cdot n^{o(1)})$, where $P$ is the returned path. This is the first $(1+epsilon)$-approximation algorithm against an adaptive adversary that supports shortest-path queries in time below $O(n)$, that breaks the $O(mn)$ total update time bound of the classical algorithm of Even and Shiloah from 1981. Our second result is a deterministic algorithm for the decremental APSP problem on unweighted graphs that achieves total update time $O(n^{2.5+delta})$, for any constant $delta>0$, supports approximate distance queries in $O(loglog n)$ time; the algorithm achieves an $O(1)$-multiplicative and $n^{o(1)}$-additive approximation on the path length. All previous algorithms for APSP either assume an oblivious adversary or have an $Omega(n^{3})$ total update time when $m=Omega(n^{2})$.
In the decremental $(1+epsilon)$-approximate Single-Source Shortest Path (SSSP) problem, we are given a graph $G=(V,E)$ with $n = |V|, m = |E|$, undergoing edge deletions, and a distinguished source $s in V$, and we are asked to process edge deletions efficiently and answer queries for distance estimates $widetilde{mathbf{dist}}_G(s,v)$ for each $v in V$, at any stage, such that $mathbf{dist}_G(s,v) leq widetilde{mathbf{dist}}_G(s,v) leq (1+ epsilon)mathbf{dist}_G(s,v)$. In the decremental $(1+epsilon)$-approximate All-Pairs Shortest Path (APSP) problem, we are asked to answer queries for distance estimates $widetilde{mathbf{dist}}_G(u,v)$ for every $u,v in V$. In this article, we consider the problems for undirected, unweighted graphs. We present a new emph{deterministic} algorithm for the decremental $(1+epsilon)$-approximate SSSP problem that takes total update time $O(mn^{0.5 + o(1)})$. Our algorithm improves on the currently best algorithm for dense graphs by Chechik and Bernstein [STOC 2016] with total update time $tilde{O}(n^2)$ and the best existing algorithm for sparse graphs with running time $tilde{O}(n^{1.25}sqrt{m})$ [SODA 2017] whenever $m = O(n^{1.5 - o(1)})$. In order to obtain this new algorithm, we develop several new techniques including improved decremental cover data structures for graphs, a more efficient notion of the heavy/light decomposition framework introduced by Chechik and Bernstein and the first clustering technique to maintain a dynamic emph{sparse} emulator in the deterministic setting. As a by-product, we also obtain a new simple deterministic algorithm for the decremental $(1+epsilon)$-approximate APSP problem with near-optimal total running time $tilde{O}(mn /epsilon)$ matching the time complexity of the sophisticated but rather involved algorithm by Henzinger, Forster and Nanongkai [FOCS 2013].
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 )$.
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 distances 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 in unweighted graphs with only $O(mn)$ total update time over all edge deletions. Their classic algorithm was the state of the art for the decremental SSSP problem for three decades, even when approximate shortest paths are allowed. A series of results showed how to improve upon $O(mn)$ if approximation is allowed, culminating in a recent breakthrough of Henzinger, Krinninger and Nanongkai [FOCS 14], who presented a $(1+epsilon)$-approximate algorithm for undirected weighted graphs whose total update time is near linear: $O(m^{1+o(1)}log(W))$, where $W$ is the ratio of the heaviest to the lightest edge weight in the graph. In this paper they posed as a major open problem the question of derandomizing their result. Until very recently, all known improvements over the Even-Shiloach algorithm were randomized and required the assumption of a non-adaptive adversary. In STOC 2016, Bernstein and Chechik showed the first emph{deterministic} algorithm to go beyond $O(mn)$ total update time: the algorithm is also $(1+epsilon)$-approximate, and has total update time $tilde{O}(n^2)$. In SODA 2017, the same authors presented an algorithm with total update time $tilde{O}(mn^{3/4})$. However, both algorithms are restricted to undirected, unweighted graphs. We present the emph{first} deterministic algorithm for emph{weighted} undirected graphs to go beyond the $O(mn)$ bound. The total update time is $tilde{O}(n^2 log(W))$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
