{"ID":2864836,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.23458","arxiv_id":"2509.23458","title":"Stochastic Embedding of Digraphs into DAGs","abstract":"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)\\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}}\\left[d_{D_{1}}(u,v)\\cdot\\boldsymbol{1}[u\\rightsquigarrow_{D_{1}}v]+d_{D_{2}}(u,v)\\cdot\\boldsymbol{1}[u\\rightsquigarrow_{D_{2}}v]\\right]\\le t\\cdot d_{G}(u,v)~. \\] 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.","short_abstract":"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\\rightsquigar...","url_abs":"https://arxiv.org/abs/2509.23458","url_pdf":"https://arxiv.org/pdf/2509.23458v1","authors":"[\"Arnold Filtser\"]","published":"2025-09-27T19:05:48Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}