Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDecremental APSP in Directed Graphs Versus an Adaptive Adversary
172
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 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].
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.
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. [...]
The Minimum Path Cover problem on directed acyclic graphs (DAGs) is a classical problem that provides a clear and simple mathematical formulation for several applications in different areas and that has an efficient algorithmic solution. In this paper, we study the computational complexity of two constrained variants of Minimum Path Cover motivated by the recent introduction of next-generation sequencing technologies in bioinformatics. The first problem (MinPCRP), given a DAG and a set of pairs of vertices, asks for a minimum cardinality set of paths covering all the vertices such that both vertices of each pair belong to the same path. For this problem, we show that, while it is NP-hard to compute if there exists a solution consisting of at most three paths, it is possible to decide in polynomial time whether a solution consisting of at most two paths exists. The second problem (MaxRPSP), given a DAG and a set of pairs of vertices, asks for a path containing the maximum number of the given pairs of vertices. We show its NP-hardness and also its W[1]-hardness when parametrized by the number of covered pairs. On the positive side, we give a fixed-parameter algorithm when the parameter is the maximum overlapping degree, a natural parameter in the bioinformatics applications of the problem.
A directed graph $D$ is semicomplete if for every pair $x,y$ of vertices of $D,$ there is at least one arc between $x$ and $y.$ viol{Thus, a tournament is a semicomplete digraph.} In the Directed Component Order Connectivity (DCOC) problem, given a digraph $D=(V,A)$ and a pair of natural numbers $k$ and $ell$, we are to decide whether there is a subset $X$ of $V$ of size $k$ such that the largest strong connectivity component in $D-X$ has at most $ell$ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $ell=1.$ We study parametered complexity of DCOC for general and semicomplete digraphs with the following parameters: $k, ell,ell+k$ and $n-ell$. In particular, we prove that DCOC with parameter $k$ on semicomplete digraphs can be solved in time $O^*(2^{16k})$ but not in time $O^*(2^{o(k)})$ unless the Exponential Time Hypothesis (ETH) fails. gutin{The upper bound $O^*(2^{16k})$ implies the upper bound $O^*(2^{16(n-ell)})$ for the parameter $n-ell.$ We complement the latter by showing that there is no algorithm of time complexity $O^*(2^{o({n-ell})})$ unless ETH fails.} Finally, we improve viol{(in dependency on $ell$)} the upper bound of G{{o}}ke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $ell+k$ on general digraphs from $O^*(2^{O(kelllog (kell))})$ to $O^*(2^{O(klog (kell))}).$ Note that Drange, Dregi and van t Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time $O^*(2^{o(klog ell)})$ unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity $O^*(2^{o(klog k)}).$
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
