Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.20471 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912089393594368 |
|---|---|
| author | Bodwin, Greg Le, Tuong |
| author_facet | Bodwin, Greg Le, Tuong |
| contents | A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an $n$-node directed input graph $G$ among a set of given demand pairs $P$ of size $|P|=p$. We give constructions of sparse reachability preservers in the online setting, where $G$ is given on input, the demand pairs $(s, t) \in P$ arrive one at a time, and we must irrevocably add edges to a preserver $H$ to ensure reachability for the pair $(s, t)$ before we can see the next demand pair. Our main results are:
-- There is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( n^{0.72}p^{0.56} + n^{0.6}p^{0.7} + n\right).$$ This improves polynomially on the previous online upper bound of $O( \min\{np^{0.5}, n^{0.5}p\}) + n$, implicit in the work of Coppersmith and Elkin [SODA '05].
-- Given a promise that the demand pairs will satisfy $P \subseteq S \times V$ for some vertex set $S$ of size $|S|=:σ$, there is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( (npσ)^{1/2} + n\right).$$ A slightly different construction gives the same result for the setting $P \subseteq V \times S$. This improves polynomially on the previous online upper bound of $O( σn)$ (folklore).
All of these constructions are polynomial time, deterministic, and they do not require knowledge of the values of $p, σ$, or $S$. Our techniques also give a small polynomial improvement in the current upper bounds for offline reachability preservers, and they extend to a stronger model in which we must commit to a path for all possible reachable pairs in $G$ before any demand pairs have been received. As an application, we improve the competitive ratio for Online Unweighted Directed Steiner Forest to $O(n^{3/5 + \varepsilon})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_20471 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved Online Reachability Preservers Bodwin, Greg Le, Tuong Data Structures and Algorithms A reachability preserver is a basic kind of graph sparsifier, which preserves the reachability relation of an $n$-node directed input graph $G$ among a set of given demand pairs $P$ of size $|P|=p$. We give constructions of sparse reachability preservers in the online setting, where $G$ is given on input, the demand pairs $(s, t) \in P$ arrive one at a time, and we must irrevocably add edges to a preserver $H$ to ensure reachability for the pair $(s, t)$ before we can see the next demand pair. Our main results are: -- There is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( n^{0.72}p^{0.56} + n^{0.6}p^{0.7} + n\right).$$ This improves polynomially on the previous online upper bound of $O( \min\{np^{0.5}, n^{0.5}p\}) + n$, implicit in the work of Coppersmith and Elkin [SODA '05]. -- Given a promise that the demand pairs will satisfy $P \subseteq S \times V$ for some vertex set $S$ of size $|S|=:σ$, there is a construction that guarantees a maximum preserver size of $$|E(H)| \le O\left( (npσ)^{1/2} + n\right).$$ A slightly different construction gives the same result for the setting $P \subseteq V \times S$. This improves polynomially on the previous online upper bound of $O( σn)$ (folklore). All of these constructions are polynomial time, deterministic, and they do not require knowledge of the values of $p, σ$, or $S$. Our techniques also give a small polynomial improvement in the current upper bounds for offline reachability preservers, and they extend to a stronger model in which we must commit to a path for all possible reachable pairs in $G$ before any demand pairs have been received. As an application, we improve the competitive ratio for Online Unweighted Directed Steiner Forest to $O(n^{3/5 + \varepsilon})$. |
| title | Improved Online Reachability Preservers |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.20471 |