Covering Approximate Shortest Paths with DAGs
Sepehr Assadi, Gary Hoppenworth, Nicole Wein · 2025
Read Covering Approximate Shortest Paths with DAGs by Sepehr Assadi, Gary Hoppenworth, Nicole Wein (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-2504-11256.txt.
Introduction
Sepehr Assadi, Gary Hoppenworth, and Nicole Wein define covers of directed graphs by acyclic graphs that keep near shortest path lengths. Tree covers do this job for undirected graphs, but directed graphs are harder. Their work came out in twenty twenty-five.
A cover is a small set of acyclic graphs where, for each pair of points, one graph gives a path close to the true shortest. If the acyclic graphs must be subgraphs, a full set is forced even for mere reach. So the authors allow extra edges. With a huge extra budget, two graphs suffice with no stretch. They prove near matching lower bounds, then give a fast method for the sparse extra edge case that fits the source graph's size.
Catalog record
| CREATOR | Sepehr Assadi, Gary Hoppenworth, Nicole Wein |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 188 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2504-11256