Covering Approximate Shortest Paths with DAGs
Covering Approximate Shortest Paths with DAGs
计算技术、计算机技术
Sepehr Assadi,Gary Hoppenworth,Nicole Wein.Covering Approximate Shortest Paths with DAGs[EB/OL].(2025-04-15)[2025-09-17].https://arxiv.org/abs/2504.11256.点此复制
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 \alpha \cdot dist_G(s,
t)$, where $\alpha$ is the distortion.
As a trivial upper bound, there is a DAG cover with $n$ DAGs and $\alpha=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 $\alpha=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.
展开英文信息
评论