Representing Distances in Directed Graphs via a Collection of DAGs

For undirected graphs, probabilistic tree embeddings have been an immensely useful graph-simplification primitive in many applications. In this work, we initiate the study of a directed analog of this problem. Specifically, instead of using a collection of trees to approximate distances, we investigate using a collection of DAGs to approximate distance in a general directed graph. Our main results are lower bounds, but we also prove upper bounds.