Stochastic Embedding of Digraphs into DAGs
Arnold Filtser Bar-Ilan University · 2025
Read Stochastic Embedding of Digraphs into DAGs by Arnold Filtser Bar-Ilan University (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-23458.txt.
Introduction
Directed graphs with cycles can be hard to reason about, so Arnold Filtser maps them into acyclic ones at random. Filtser, the sole author, defines a stochastic embedding as a random pair of directed acyclic graphs. For every pair of vertices, reachability must survive in exactly one of the two graphs. Distances in the graphs must never shrink below the true distance.
Filtser builds such an embedding with expected distortion growing only like the log of the vertex count, times small factors. The graphs stay sparse, with edge counts near the original. Sampling from the scheme is fast as well. The result improves a prior bound from Assadi, Hoppenworth, and Wein, which had a cubed log factor.
Catalog record
| CREATOR | Arnold Filtser Bar-Ilan University |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 171 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-23458