Covering Approximate Shortest Paths with DAGs
Sepehr Assadi Gary Hoppenworth Nicole Wein
作者信息
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 \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.引用本文复制引用
Sepehr Assadi,Gary Hoppenworth,Nicole Wein.Covering Approximate Shortest Paths with DAGs[EB/OL].(2025-04-15)[2025-12-31].https://arxiv.org/abs/2504.11256.学科分类
计算技术、计算机技术
|国家预印本平台
评论