Tree Covers for Directed Graphs: Distance Oracles, Routing Schemes and Spanners

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(kn1/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 distG(u v) = distG(u → v) + distG(v → u) denote the roundtrip distance. For every integer k, we construct a collection T of tree-pairs, each consisting of an in-tree and an out-tree rooted at the same vertex. Each vertex belongs to O(kn1/k) tree-pairs in expectation, and for every ordered pair $(u, v)$ some tree-pair Tᵢₙ∪ Tₒᵤₜ ∈ T satisfies dist_Tᵢₙ∪ Tₒᵤₜ(u → v) ≤ distG(u → v) + (k-1)distG(u v). We call this a 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 ≥ 4, all the above objects can be constructed in O(min, n2.5\) expected time, breaking the $mn$ barrier in dense directed graphs.