This paper provides a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities and introduces two new instructive techniques and demonstrates how to utilize them to construct several new algorithms.
Abstract
The sensitivity setting is a restricted setting for dynamic algorithms, particularly practical for scenarios where extensive preprocessing is feasible but responses to real-time modifications must be near-instantaneous before the data structure is eventually rebuilt. For graph problems, a sensitivity data structure is constructed with a preprocessing time P so that the following queries can be answered quickly, preferably in $O(1)$ time: given an edge $e$, return the answer to the problem on either $G \setminus e$ (decremental) or $G \cup e$ (incremental). In this paper, we almost entirely settle the decremental setting for the diameter and eccentricities problems in a variety of approximation regimes by matching P to the static runtime while supporting $O(1)$-time queries, thereby improving upon all previous results for a single failure [Bil\`o, Cohen, Friedrich, Schirneck, MFCS 2021; Bil\`o, Choudhary, Cohen, Friedrich, Krogmann, Schirneck, ICALP 2021]. More precisely: (1) We provide a tight reduction demonstrating that any exact distance sensitivity oracle can be used to efficiently solve decremental exact diameter and all-node eccentricities; (2) For the approximate setting, we match the runtime of all known static diameter algorithms across all sparsity settings, up to an additional $1+o(1)$ factor in approximation. Conversely, for the previously unexplored incremental setting of these problems: (3) We develop new lower bounds, demonstrating that no incremental algorithm can efficiently approximate diameter, radius, or eccentricity beyond a $5/3$ factor in undirected graphs or a $2$ factor in directed graphs; (4) We introduce two new instructive techniques and demonstrate how to utilize them to construct several new algorithms. Most notably, we develop incremental single-node eccentricity approximations for both directed and undirected graphs that match our new lower bounds.
A randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions is given, which follows from a simple stability principle for partially dynamic graphs.
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.· 0 citations
This paper asks what structural properties of the graph itself make metric repair tractable, and gives pseudo-polynomial time algorithms for series-parallel graphs, and by generalization, graphs of bounded treewidth and a new algorithm for the length-bounded multicut problem.
Asaf Etgar, A. Gilbert, Jamie Tucker-Foltz· arXiv.org· 0 citations
Sensitivity oracles preprocess a graph so that queries can be answered after any $f$ edge insertions and deletions, without recomputing from scratch. For structural optimization problems the known landscape is limited: for flows and cuts, all known compact oracles handle only $f\le2$ failures; existing oracles for $s$- and global min-cut apply only to undirected graphs; and for matchings, arborescence and spanning-tree packings, and arboricity, no efficient oracle is known for $f>1$. We present a unified algebraic framework based on sensitivity oracles for matroid packing, covering, and parity of sparse linear matroids, yielding the first oracles supporting an arbitrary number $f$ of updates across all of these problems (all constructions randomized Monte-Carlo). Concretely, we obtain efficient oracles for exact $(s,t)$-max-flow/min-cut, resolving an open problem of Baswana, Bhanja, and Pandey (ICALP'22) with near-optimal space; for all-pairs $k$-bounded flow, generalizing the near-optimal reachability oracle of Brand and Saranurak (FOCS'19, the case $k=1$); the first oracles for any $f$ for directed $s$- and global min-cut; oracles for $k$-disjoint arborescences, $k$-disjoint spanning trees, colorful spanning trees, and arboricity; and oracles for the existence of an $\alpha$-factor, with perfect matching as the case $\alpha=1$. We further introduce the \emph{subset sensitivity model}, in which updates are confined to a susceptible edge set of size $\sigma$ fixed during preprocessing. Here we decouple updates from the matroid representation and eliminate the dependence on $k$ and the matroid density altogether: all of the above are supported with $\widetilde O(f^\omega)$ query time and $O(f\sigma^2)$ space. We also prove a matching $\Omega(\min\{\sigma^2,n^2\})$-bit lower bound when $f\ge2$, establishing optimality.
Keerti Choudhary, Amit Kumar, Lakshay Saggi· 0 citations
This paper provides the first truly linear-time approximation scheme for the Densest Subgraph Problem, and uses assignments arising from a flow-based formulation together with a structural carving lemma to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph.
Navigability is a fundamental property of graph-based search structures and plays an important role in the analysis of nearest-neighbor algorithms. Informally, a graph is navigable if, from any current point and toward any desired target, there is always an outgoing edge that moves strictly closer to that target. While this property provides a strong guarantee for greedy search, it can be inherently expensive: in the worst case, navigable graphs require $\Omega(n^{3/2})$ edges, where $n$ is the size of the dataset. Recently, Avi and Musco introduced $(1-\epsilon)$-almost navigability, a natural relaxation in which, from every current point, such a progress-making edge is required for almost all targets, while an $\epsilon$ fraction of targets may fail this condition \cite{avimusco2026almost}. They showed that every dataset admits such a graph with $O(n/\epsilon)$ edges. In this work, we prove a matching lower bound, establishing the optimality of their construction and giving a complete characterization of the sparsity achievable by almost-navigable graphs. For most values of $\epsilon$, our hard instances lie in Euclidean spaces of polylogarithmic dimension, across the full worst-case range of $\epsilon $, dimension $d=O(\sqrt{n}\log^{3/2} n)$ suffices. The same construction also sharpens our understanding of ordinary navigability: in the latter dimension, we exhibit datasets for which every navigable graph has $\Omega(n^{3/2})$ edges. Our proof reveals a surprising connection between almost navigability and the classical Zarankiewicz problem of constructing dense graphs with limited pairwise neighborhood overlap. This connection lets us translate extremal graph constructions into hard geometric instances for navigation, linking two seemingly different notions of graph sparsity.
