Directed graph tree covers improve distances routing and spanners
Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners
Data Structures and Algorithms
Summary
Measuring distances and finding good routes in one-way networks (directed graphs) is tricky because paths may not easily reverse. The authors extended a famous method that worked well for two-way networks to these one-way cases. They built a set of special tree structures that cover the network and help approximate the shortest paths with limited extra distance. This helps create faster tools for answering distance questions, routing data, and simplifying the network, with strong efficiency even for large networks.
What this means in practice
- •For network engineers: Construct compact routing schemes for directed networks enabling efficient near-shortest path routing with reduced memory and query costs.
- •For database system developers: Build fast distance oracles to quickly approximate roundtrip distances in large directed data graphs for query optimization and analytics.
Authors
Shiri Chechik, Gur Lifshitz
Abstract
In a seminal work [STOC'01; JACM'05], Thorup and Zwick showed that every weighted undirected graph admits a tree cover where each vertex belongs to $O(kn^{1/k})$ trees in expectation, and every pair has a path of stretch at most $2k-1$ in some tree. In this paper, we extend this structural property to directed graphs with nonnegative edge weights. Let $\mathrm{dist}_G(u \leftrightarrows v) = \mathrm{dist}_G(u \to v) + \mathrm{dist}_G(v \to u)$ denote the roundtrip distance. For every integer $k$, we construct a collection $\mathcal{T}$ of tree-pairs, each consisting of an in-tree and an out-tree rooted at the same vertex. Each vertex belongs to $O(kn^{1/k})$ tree-pairs in expectation, and for every ordered pair $(u, v)$ some tree-pair $T_{in}\cup T_{out} \in \mathcal{T}$ satisfies $\mathrm{dist}_{T_{in}\cup T_{out}}(u \to v) \le \mathrm{dist}_G(u \to v) + (k-1)\mathrm{dist}_G(u \leftrightarrows v).$ We call this a \emph{$k$-strong (roundtrip) tree cover}. While prior techniques partition distances into geometric scales and build separate structures for each scale, our construction handles all distances simultaneously within a single, unified hierarchy. This yields the first directed tree cover for general $k$ matching the classic Thorup-Zwick stretch-size trade-off. Our cover immediately implies improved constructions of roundtrip spanners, path-reporting distance oracles, and compact routing schemes, as well as their source-wise and prioritized variants. We also provide faster algorithms for these structures: for general $k \ge 4$, all the above objects can be constructed in $\widetilde{O}(\min\{mn, n^{2.5}\})$ expected time, breaking the $mn$ barrier in dense directed graphs.