Daniel Dadush

Ben Bals, Joakim Blikstad, Greg Bodwin et al.

For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentially optimal tradeoffs between size and quality. The goal of this paper is to develop and analyze comparable greedy algorithms for nearby objects in graph metric augmentation. We show the following: - A simple greedy algorithm for shortcut sets achieves the state-of-the-art size/hopbound tradeoff recently proved by Kogan and Parter (2022), up to $O(\log n)$ factors in the size. Moreover, with an additional preprocessing step, the greedy algorithm subpolynomially improves on the previous size bounds in some range of parameters. - The same greedy algorithm was already known to be existentially optimal for the size/hopbound tradeoff for hopsets, by an analysis of Berman, Raskhodnikova, and Ruan (2010) introduced for transitive-closure spanners. We provide a completely different analysis showing that the algorithm is also existentially optimal (up to $O(\log n)$ factors) for the matching hopset problem, in which one has a budget of roughly $O(m)$ additional edges (for an $m$-edge input graph).

Daniel Dadush, Michał Pilipczuk, Amadeus Reinald et al.

Fix a parameter $k\in \mathbf{N}$. We give dynamic data structures that for a fully dynamic undirected graph $G$, updated over time by edge insertions and edge deletions, can answer the following queries: - Long $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $k$? - Long $(u,v)$-detour: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of length at least $\text{dist}_G(u,v)+k$? - Even/odd $(u,v)$-path: Given $u,v\in V(G)$, is there a path from $u$ to $v$ of even/odd length? The amortized time of executing an update or answering a query is $2^{O(k^3)} \log n + O(\log^2 n \log^2 \log n)$ in the first two cases, and $O(\log^2 n \log^2 \log n)$ in the last, where $n$ is the number of vertices of $G$. The first result is in sharp contrast with known conditional lower bounds for reporting paths of length at most $k$. Specifically, there is no data structure supporting queries about $(u,v)$-paths of length at most two in time $n^{o(1)}$ unless the Triangle Conjecture fails. Our main technical contribution is a mechanism of "delayed edge insertion" that works locally on the level of biconnected components.