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\), \begin{equation} \mathbb{E}_{(D_1, D_2) \sim \mathcal{D}}\left[ d_{D_1}(u,v)\cdot \mathbb{1}[u \rightsquigarrow_{D_1} v] + d_{D_2}(u,v)\cdot \mathbb{1}[u \rightsquigarrow_{D_2} v]\right]\le t \cdot d_G(u,v)\,.\end{equation} Finally, the sparsity of \(\mathcal D\) is the maximum number of edges in any of the DAGs in its support.