A Note on Distance-Preserving Graph Sparsification

DOI10.1016/J.IPL.2021.106205MaRDI QIDQ6333272arXivFDO

Authors Greg Bodwin

Publication date 21 January 2020

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.IPL.2021.106205

Mathematics Subject Classification ID

Distance in graphs (05C12) Density (toughness, etc.) (05C42) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.DSmath.CO

Abstract: We consider problems of the following type: given a graph $G$, how many edges are needed in the worst case for a sparse subgraph $H$ that approximately preserves distances between a given set of node pairs $P$? Examples include pairwise spanners, distance preservers, reachability preservers, etc. There has been a trend in the area of simple constructions based on the hitting set technique, followed by somewhat more complicated constructions that improve over the bounds obtained from hitting sets by roughly a $log$ factor. In this note, we point out that the simpler constructions based on hitting sets don't actually need an extra $log$ factor in the first place. This simplifies and unifies a few proofs in the area, and it improves the size of the $+4$ pairwise spanner from $widetildeO(n{p}^{2/7})$ [Kavitha Th. Comp. Sys. '17] to $O(n{p}^{2/7})$.

This page was built for publication: A Note on Distance-Preserving Graph Sparsification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6333272)