Theory Lunch Seminar - Gary Hoppenworth April 16, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 8102 Speaker: GARY HOPPENWORTH , Ph.D. Student in Computer Science, Computer Science and Engineering, University of Michigan https://web.eecs.umich.edu/~garytho/ Covering Approximate Shortest Paths with DAGs We define and study analogs of probabilistic tree embeddings and tree covers 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] \ distDi(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 n2 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 n2-o(1) additional edges, at least n1-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 asymptotically 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. 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. Finally, we point out that our DAG cover upper bounds have implications for a variety of combinatorial and algorithmic problems related to approximate shortest paths in directed graphs. This talk is based on joint work with Sepehr Assadi and Nicole Wein. Event Website: https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20250416.html Add event to Google Add event to iCal
