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 \rightsquigarrow_{G}\ v$ (i.e., $v$ is reachable from $u$ in $G$) implies that $u \rightsquigarrow_{D_1} v$ or $u \rightsquigarrow_{D_2} v$ (but not both), and (2) distances are dominated: $d_G(u, v) = \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$, equation E_(D_1, D_2) D + d_D_2(u,v)1[u _D_2 v]]t d_G(u,v) .equation Finally, the sparsity of $\mathcal D$ is the maximum number of edges in any of the DAGs in its support.