Shortcuts and Transitive-Closure Spanners Approximation

Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai · 2025

Read Shortcuts and Transitive-Closure Spanners Approximation by Parinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai (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-2502-08032.txt.

Description

Parinya Chalermsook and co-authors wrote a 2025 paper on adding shortcut edges to directed graphs. A shortcut set adds edges so any node can reach any other in few hops, while keeping the same reachability. A close cousin, the transitive-closure spanner, swaps in a sparse edge set with small diameter. Both help speed routing and queries.

The authors study approximation methods that run in polynomial time. Given a graph with a good small solution, the method must find one not much worse. They bound how far the size and diameter can slip. Under a standard conjecture, no method can do much better. The results map the limits of fast graph compression.

Catalog record

CREATORParinya Chalermsook, Yonggang Jiang, Sagnik Mukhopadhyay, Danupon Nanongkai
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE103 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-08032

Browse the full library · About the Tower of Babel