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

CREATORArnold Filtser Bar-Ilan University
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE171 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-23458

Browse the full library · About the Tower of Babel