Reachability Preservers: New Extremal Bounds and Approximation Algorithms
SIAM Journal on Computing · 30.04.2024 · 53 (2) · 221-246
DOI: 10.1137/21m1442176 ↗Kurz gefasst
Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 13.03.2024. Verfasst von Amir Abboud und 1 weiteren Autor:innen. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 54 Literaturangaben. Gefördert von: National Science Foundation, United States - Israel Binational Science Foundation.
Abstract (Originalsprache)
We define and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph [Formula: see text] and a set of demand pairs [Formula: see text], a reachability preserver is a sparse subgraph [Formula: see text] that preserves reachability between all demand pairs Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an [Formula: see text]-node graph and demand pairs of the form [Formula: see text] for a small node subset [Formula: see text], there is always a reachability preserver on [Formula: see text] edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which [Formula: see text] size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the [Formula: see text] of Chlamtáč et al. [ Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534–553] to [Formula: see text].
Förderung
- National Science Foundation
- United States - Israel Binational Science Foundation
Zitieren
APA
Abboud, A., & Bodwin, G. (2024). Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SIAM Journal on Computing, 53(2), 221-246. https://doi.org/10.1137/21m1442176
Vancouver
Abboud A, Bodwin G. Reachability Preservers: New Extremal Bounds and Approximation Algorithms. SIAM Journal on Computing. 2024;53(2):221-246. doi:10.1137/21m1442176
BibTeX
@article{Abboud2024,
author = {Abboud, Amir and Bodwin, Greg},
title = {Reachability Preservers: New Extremal Bounds and Approximation Algorithms},
journal = {SIAM Journal on Computing},
year = {2024},
volume = {53},
number = {2},
pages = {221--246},
doi = {10.1137/21m1442176}
}
EUVIMED