196,322 research outputs found
Approximate Distance Sensitivity Oracles in Subquadratic Space
No full textAn f-edge fault-tolerant distance sensitive oracle (f-DSO) with stretch σ ≥ 1 is a data structure that preprocesses a given undirected, unweighted graph G with n vertices and m edges, and a positive integer f. When queried with a pair of vertices s, t and a set F of at most f edges, it returns a σ-approximation of the s-t-distance in G-F. We study f-DSOs that take subquadratic space. Thorup and Zwick [JACM2015] showed that this is only possible for σ ≥ 3. We present, for any constant f ≥ 1 and α (0, 1/2), and any ε > 0, an f-DSO with stretch 3 + that takes O(n2-α/f+1/ε) · O(logn/ε)f+1 space and has an O(nα/ε2) query time. We also give an improved construction for graphs with diameter at most D. For any constant k, we devise an f-DSO with stretch 2k-1 that takes O(Df+o(1) n1+1/k) space and has O(Do(1)) query time, with a preprocessing time of O(Df+o(1) mn1/k). Chechik, Cohen, Fiat, and Kaplan [SODA 2017] presented an f-DSO with stretch 1+ and preprocessing time O(n5) · O(logn/ε)f, albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to O(mn2) · O(logn/ε)f
Faster Algorithms for Dual-Failure Replacement Paths
No full textGiven a simple weighted directed graph G = (V, E, ω) on n vertices as well as two designated terminals s, t ∈ V, our goal is to compute the shortest path from s to t avoiding any pair of presumably failed edges f₁, f₂ ∈ E, which is a natural generalization of the classical replacement path problem which considers single edge failures only.
This dual failure replacement paths problem was recently studied by Vassilevska Williams, Woldeghebriel and Xu [FOCS 2022] who designed a cubic time algorithm for general weighted digraphs which is conditionally optimal; in the same paper, for unweighted graphs where ω ≡ 1, the authors presented an algebraic algorithm with runtime Õ(n^{2.9146}), as well as a conditional lower bound of n^{8/3-o(1)} against combinatorial algorithms. However, it was unknown in their work whether fast matrix multiplication is necessary for a subcubic runtime in unweighted digraphs.
As our primary result, we present the first truly subcubic combinatorial algorithm for dual failure replacement paths in unweighted digraphs. Our runtime is Õ(n^{3-1/18}). Besides, we also study algebraic algorithms for digraphs with small integer edge weights from {-M, -M+1, ⋯, M-1, M}. As our secondary result, we obtained a runtime of Õ(Mn^{2.8716}), which is faster than the previous bound of Õ(M^{2/3}n^{2.9144} + Mn^{2.8716}) from [Vassilevska Williams, Woldeghebriela and Xu, 2022]
Simplifying and Unifying Replacement Paths Algorithms in Weighted Directed Graphs
No full textIn the replacement paths (RP) problem we are given a graph G and a shortest path P between two nodes s and t . The goal is to find for every edge e ∈ P, a shortest path from s to t that avoids e. The first result of this paper is a simple reduction from the RP problem to the problem of computing shortest cycles for all nodes on a shortest path.
Using this simple reduction we unify and extremely simplify two state of the art solutions for two different well-studied variants of the RP problem.
In the first variant (algebraic) we show that by using at most n queries to the Yuster-Zwick distance oracle [FOCS 2005], one can solve the the RP problem for a given directed graph with integer edge weights in the range [-M,M] in Õ(M n^ω) time . This improves the running time of the state of the art algorithm of Vassilevska Williams [SODA 2011] by a factor of log⁶n.
In the second variant (planar) we show that by using the algorithm of Klein for the multiple-source shortest paths problem (MSSP) [SODA 2005] one can solve the RP problem for directed planar graph with non negative edge weights in O (n log n) time. This matches the state of the art algorithm of Wulff-Nilsen [SODA 2010], but with arguably much simpler algorithm and analysis
Improved Distance (Sensitivity) Oracles with Subquadratic Space
No full textA distance oracle (DO) for a graph G is a data structure that, when queried with vertices s,t, returns an estimate d(s,t) of their distance in G. The oracle has stretch (α, β) if the estimate satisfies d(s,t)≤ d(s,t)≤ α· d(s,t)+β. An f-edge} fault-tolerant distance sensitivity oracle (f-DSO}) additionally receives a set f of up to f edges and estimates the distance in G-F. Our first contribution is the design of new distance oracles with subquadratic space for undirected graphs. We show that introducing a small additive stretch β > 0 allows one to make the multiplicative stretch α arbitrarily small. This sidesteps a known lower bound of α≥slant 3 (for β=0 and subquadratic space) [Thorup & Zwick, JACM 2005]. We present a DO for graphs with edge weights in [0, W] that, for any positive integer l and any c\in(0,l/2], has stretch (1+1/l,2W), space O(n2-c/l), and query time O(nc), generalizing results by Agarwal and Godfrey [SODA 2013] to arbitrarily dense graphs. Our second contribution is a framework that turns an (α,β)- stretch} DO for unweighted graphs into an (α(1+ε),β)-stretch}. f-DSO} with sensitivity f=o(log(n)/loglog n) retaining sub-quadratic space. This generalizes a result by Bilò, Chechik, Choudhary, Cohen, Friedrich, Krogmann, and Schirneck [TheoretiCS 2024]. Combining the framework with our new DO gives an f-DSO that, for any γ(0, (l+1)/2], has stretch ((1+1/l)(1+ε), 2), space n2-γ(t+1)(f+1)}+o(1)/εf+2, and query time O(nγ/ε2). This is the first f-DSO} with subquadratic space, near-additive stretch, and sublinear query time
Approximate Distance Sensitivity Oracles in Subquadratic Space
No full textAn -edge fault-tolerant distance sensitive oracle (-DSO) with stretch is a data structure that preprocesses a given undirected, unweighted graph with vertices and edges, and a positive integer . When queried with a pair of vertices and a set of at most edges, it returns a -approximation of the --distance in .
We study -DSOs that take subquadratic space. Thorup and Zwick [JACM 2005] showed that this is only possible for . We present, for any constant and , and any , a randomized -DSO with stretch that w.h.p. takes space and has an query time. The time to build the oracle is . We also give an improved construction for graphs with diameter at most . For any positive integer , we devise an -DSO with stretch that w.h.p. takes space and has query time, with a preprocessing time of .
Chechik, Cohen, Fiat, and Kaplan [SODA 2017] devised an -DSO with stretch and preprocessing time , albeit with a super-quadratic space requirement. We show how to reduce their preprocessing time to .The is the arXiv version of the eponymous paper that appeared first at STOC 2023 and then was extended to a journal version, published in TheoretiC
Near Optimal Algorithm for the Directed Single Source Replacement Paths Problem
No full textIn the Single Source Replacement Paths (SSRP) problem we are given a graph G = (V, E), and a shortest paths tree K̂ rooted at a node s, and the goal is to output for every node t ∈ V and for every edge e in K̂ the length of the shortest path from s to t avoiding e.
We present an Õ(m√n + n²) time randomized combinatorial algorithm for unweighted directed graphs. Previously such a bound was known in the directed case only for the seemingly easier problem of replacement path where both the source and the target nodes are fixed.
Our new upper bound for this problem matches the existing conditional combinatorial lower bounds. Hence, (assuming these conditional lower bounds) our result is essentially optimal and completes the picture of the SSRP problem in the combinatorial setting.
Our algorithm naturally extends to the case of small, rational edge weights. In the full version of the paper, we strengthen the existing conditional lower bounds in this case by showing that any O(mn^(1/2-ε)) time (combinatorial or algebraic) algorithm for some fixed ε > 0 yields a truly sub-cubic algorithm for the weighted All Pairs Shortest Paths problem (previously such a bound was known only for the combinatorial setting)
Decremental single-source reachability and strongly connected components in Õ(m√n) total update time
No full textWe present randomized algorithms with a total update time of Õ(m √n) for the problems of decremental single source reachability and decremental strongly connected components on directed graphs. This improves recent breakthrough results of Henzinger, Krinninger and Nanongkai [STOC 14, ICALP 15]. In addition, our algorithms are arguably simpler
A verification-driven framework for iterative design of controllers
No full textpeer reviewedControllers often are large and complex reactive software systems and thus they typically cannot be developed as monolithic products. Instead, they are usually comprised of multiple components that interact to provide the desired functionality. Components themselves can be complex and in turn be decomposed into multiple sub-components. Designing such systems is complicated and must follow systematic approaches, based on recursive decomposition strategies that yield a modular structure. This paper proposes FIDDle–a comprehensive verification-driven framework which provides support for designers during development. FIDDle supports hierarchical decomposition of components into sub-components through formal specification in terms of pre- and post-conditions as well as independent development, reuse and verification of sub-components. The framework allows the development of an initial, partially specified design of the controller, in which certain components, yet to be defined, are precisely identified. These components can be associated with pre- and post-conditions, i.e., a contract, that can be distributed to third-party developers. The framework ensures that if the components are compliant with their contracts, they can be safely integrated into the initial partial design without additional rework. As a result, FIDDle supports an iterative design process and guarantees correctness of the system at any step of development. We evaluated the effectiveness of FIDDle in supporting an iterative and incremental development of components using the K9 Mars Rover example developed at NASA Ames. This can be considered as an initial, yet substantive, validation of the approach in a realistic setting. We also assessed the scalability of FIDDle by comparing its efficiency with the classical model checkers implemented within the LTSA toolset. Results show that FIDDle scales as well as classical model checking as the number of the states of the components under development and their environments grow
Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
No full textIn this work we derandomize two central results in graph algorithms, replacement paths and distance sensitivity oracles (DSOs) matching in both cases the running time of the randomized algorithms.
For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The replacement paths problem is to find for every edge e in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of O~(m sqrt{n}). Here we provide the first deterministic algorithm for this problem, with the same O~(m sqrt{n}) time. Due to matching conditional lower bounds of Williams et al. [FOCS 2010], our deterministic combinatorial algorithm for the replacement paths problem is optimal up to polylogarithmic factors (unless the long standing bound of O~(mn) for the combinatorial boolean matrix multiplication can be improved). This also implies a deterministic algorithm for the second simple shortest path problem in O~(m sqrt{n}) time, and a deterministic algorithm for the k-simple shortest paths problem in O~(k m sqrt{n}) time (for any integer constant k > 0).
For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with real-edge weights. An f-Sensitivity Distance Oracle (f-DSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a data-structure, such that given a query (s,t,F) with s,t in V and F subseteq E cup V, |F| <=f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \ F (i.e., the distance from s to t in the graph G after removing from it the failing edges and vertices F).
For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented several randomized f-DSOs. In particular, they presented a combinatorial f-DSO with O~(mn^{4-alpha}) preprocessing time and subquadratic O~(n^{2-2(1-alpha)/f}) query time, giving a tradeoff between preprocessing and query time for every value of 0 < alpha < 1. We derandomize this result and present a combinatorial deterministic f-DSO with the same asymptotic preprocessing and query time
EPR investigations of organic non-covalent assemblies with spin labels and spin probes
No full textThe object of the present report is to review the articles appeared in the literature in the last few years describing the use of EPR spectroscopy to investigate the properties of purely organic non-covalent assemblies in liquid solution with spin labels and spin probes
- …
