Stochastic Embedding of Digraphs into DAGs

Given a weighted digraph $G=(V,E,w)$, a stochastic embedding into DAGs is a distribution $\mathcal{D}$ over pairs of DAGs $(D_1,D_2)$ such that for every $u,v$: (1) the reachability is preserved: $u{⇝}_{G}v$ (i.e., $v$ is reachable from $u$ in $G$) implies that $u{⇝}_{D_1}v$ or $u{⇝}_{D_2}v$ (but not both), and (2) distances are dominated: $d_G(u,v)\le \min \{d_{D_1}(u,v),d_{D_2}(u,v)\}$. The stochastic embedding $\mathcal{D}$ has expected distortion $t$ if for every $u,v\in V$, $${\mathbb{E}}_{(D_1,D_2)\sim \mathcal{D}}[d_{D_1}(u,v)\cdot \mathbf{1}[u{⇝}_{D_1}v]+d_{D_2}(u,v)\cdot \mathbf{1}[u{⇝}_{D_2}v]]\le t\cdot d_G(u,v)\mathrm{.}$$ Finally, the sparsity of $\mathcal{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 $\tilde{O}(\log n)$ and $\tilde{O}(m)$ sparsity, improving a previous result by Assadi, Hoppenworth, and Wein [STOC 25], which achieved expected distortion $\tilde{O}({\log }^{3}n)$. Further, we can sample DAGs from this distribution in $\tilde{O}(m)$ time.