# Covering Approximate Shortest Paths with DAGs

Preprint · Sepehr Assadi, Gary Hoppenworth, Nicole Wein

- Archive id: arxiv:2504.11256
- Published: 2025-04-15
- arXiv: https://arxiv.org/abs/2504.11256
- Source URL: https://arxiv.org/abs/2504.11256
- PDF: https://arxiv.org/pdf/2504.11256
- Provenance: arxiv

## Abstract

We define and study analogs of probabilistic tree embedding and tree cover for directed graphs. We define the notion of a DAG cover of a general directed graph $G$: a small collection $D\_1,\\dots D\_g$ of DAGs so that for all pairs of vertices $s,t$, some DAG $D\_i$ provides low distortion for $dist(s,t)$; i.e. $ dist\_G(s, t) \\le \\min\_{i \\in \[g\]} dist\_{D\_i}(s, t) \\leq α\\cdot dist\_G(s, t)$, where $α$ is the distortion. As a trivial upper bound, there is a DAG cover with $n$ DAGs and $α=1$ by taking the shortest-paths tree from each vertex. When each DAG is restricted to be a subgraph of $G$, there is a matching lower bound (via a directed cycle) that $n$ DAGs are necessary, even to preserve reachability. Thus, we allow the DAGs to include a limited number of additional edges not in the original graph. When $n^2$ additional edges are allowed, there is a simple upper bound of two DAGs and $α=1$. Our first result is an almost-matching lower bound that even for $n^{2-o(1)}$ additional edges, at least $n^{1-o(1)}$ DAGs are needed, even to preserve reachability. However, the story is different when the number of additional edges is $\\tilde{O}(m)$, a natural setting where the sparsity of the DAG collection nearly matches the original graph. Our main upper bound is that there is a near-linear time algorithm to construct a DAG cover with $\\tilde{O}(m)$ additional edges, polylogarithmic distortion, and only $O(\\log n)$ DAGs. This is similar to known results for undirected graphs: the well-known FRT probabilistic tree embedding implies a tree cover where both the number of trees and the distortion are logarithmic. Our algorithm also extends to a certain probabilistic embedding guarantee. Lastly, we complement our upper bound with a lower bound showing that achieving a DAG cover with no distortion and $\\tilde{O}(m)$ additional edges requires a polynomial number of DAGs.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.