Covering Approximate Shortest Paths with DAGs

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 D1, . . . Dg of DAGs so that for all pairs of vertices s, t, some DAG Di provides low distortion for dist(s, t); i.e. distG(s, t) ≤ min i∈[g] distD i (s, t) ≤ α • distG(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 simple 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 from 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 Õ(m), a natural setting where the sparsity of the DAG collection nearly matches that of the original graph. Our main upper bound is that there is a near-linear time algorithm to construct a DAG cover with Õ(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 Õ(m) additional edges requires a polynomial number of DAGs.