Covering Approximate Shortest Paths with DAGs

Sepehr Assadi, Gary Hoppenworth, Nicole Wein

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 collect…