Stochastic Embedding of Digraphs into DAGs

Given a weighted digraph $G=(V,E,w)$, a stochastic embedding into DAGs is a distribution D over pairs of DAGs (D₁,D₂) such that for every $u,v$: (1) the reachability is preserved: uG v (i.e., v is reachable from u in G) implies that uD₁ v or uD₂ v (but not both), and (2) distances are dominated: dG(u,v)≤min₁(u,v),dD₂(u,v)\. The stochastic embedding D has expected distortion t if for every u,v∈ V, \[ E_{(D₁,D₂)}[d_{D₁}(u,v)·1[u_{D₁}v]+d_{D₂}(u,v)·1[u_{D₂}v]]≤ t· dG(u,v)~. \] Finally, the sparsity of D is the maximum number of edges in any of the DAGs in its support. Given an n vertex digraph with m edges, we construct a stochastic embedding into DAGs with expected distortion Õ(log n) and Õ(m) sparsity, improving a previous result by Assadi, Hoppenworth, and Wein [STOC 25], which achieved expected distortion Õ(log³ n). Further, we can sample DAGs from this distribution in Õ(m) time.