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

CREATORSepehr Assadi, Gary Hoppenworth, Nicole Wein
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE188 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-11256

Browse the full library · About the Tower of Babel