Better Distance Preservers and Additive Spanners
<jats:p> We study two popular ways to sketch the shortest path distances of an input graph. The first is <jats:italic>distance preservers</jats:italic> , which are sparse subgraphs that agree with the distances of the original graph on a given...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/143945 |
| _version_ | 1826199611528708096 |
|---|---|
| author | Bodwin, Greg Williams, Virginia Vassilevska |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Bodwin, Greg Williams, Virginia Vassilevska |
| author_sort | Bodwin, Greg |
| collection | MIT |
| description | <jats:p>
We study two popular ways to sketch the shortest path distances of an input graph. The first is
<jats:italic>distance preservers</jats:italic>
, which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called
<jats:italic>consistency</jats:italic>
, stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any
<jats:italic>p</jats:italic>
demand pairs in an
<jats:italic>n</jats:italic>
-node undirected unweighted graph have a distance preserver on O(
<jats:italic>n</jats:italic>
<jats:sup>2/3</jats:sup>
<jats:italic>p</jats:italic>
<jats:sup>2/3</jats:sup>
+
<jats:italic>np</jats:italic>
<jats:sup>1/3</jats:sup>
edges. We leave a conjecture that the right bound is
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
<jats:sup>2/3</jats:sup>
<jats:italic>p</jats:italic>
<jats:sup>2/3</jats:sup>
+
<jats:italic>n</jats:italic>
) or better.
</jats:p>
<jats:p>
The second part of this paper leverages these distance preservers in a new construction of
<jats:italic>additive spanners</jats:italic>
, which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on
<jats:italic>O(n)</jats:italic>
edges with +
<jats:italic>O</jats:italic>
(
<jats:italic>n</jats:italic>
<jats:sup>3/7 + ε</jats:sup>
) error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii.
</jats:p> |
| first_indexed | 2024-09-23T11:22:41Z |
| format | Article |
| id | mit-1721.1/143945 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:22:41Z |
| publishDate | 2022 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1439452023-04-11T19:53:13Z Better Distance Preservers and Additive Spanners Bodwin, Greg Williams, Virginia Vassilevska Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science <jats:p> We study two popular ways to sketch the shortest path distances of an input graph. The first is <jats:italic>distance preservers</jats:italic> , which are sparse subgraphs that agree with the distances of the original graph on a given set of demand pairs. Prior work on distance preservers has exploited only a simple structural property of shortest paths, called <jats:italic>consistency</jats:italic> , stating that one can break shortest path ties such that no two paths intersect, split apart, and then intersect again later. We prove that consistency alone is not enough to understand distance preservers, by showing both a lower bound on the power of consistency and a new general upper bound that polynomially surpasses it. Specifically, our new upper bound is that any <jats:italic>p</jats:italic> demand pairs in an <jats:italic>n</jats:italic> -node undirected unweighted graph have a distance preserver on O( <jats:italic>n</jats:italic> <jats:sup>2/3</jats:sup> <jats:italic>p</jats:italic> <jats:sup>2/3</jats:sup> + <jats:italic>np</jats:italic> <jats:sup>1/3</jats:sup> edges. We leave a conjecture that the right bound is <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>2/3</jats:sup> <jats:italic>p</jats:italic> <jats:sup>2/3</jats:sup> + <jats:italic>n</jats:italic> ) or better. </jats:p> <jats:p> The second part of this paper leverages these distance preservers in a new construction of <jats:italic>additive spanners</jats:italic> , which are subgraphs that preserve all pairwise distances up to an additive error function. We give improved error bounds for spanners with relatively few edges; for example, we prove that all graphs have spanners on <jats:italic>O(n)</jats:italic> edges with + <jats:italic>O</jats:italic> ( <jats:italic>n</jats:italic> <jats:sup>3/7 + ε</jats:sup> ) error. Our construction can be viewed as an extension of the popular path-buying framework to clusters of larger radii. </jats:p> 2022-07-21T17:13:17Z 2022-07-21T17:13:17Z 2021 2022-07-21T17:03:31Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/143945 Bodwin, Greg and Williams, Virginia Vassilevska. 2021. "Better Distance Preservers and Additive Spanners." ACM Transactions on Algorithms, 17 (4). en 10.1145/3490147 ACM Transactions on Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Bodwin, Greg Williams, Virginia Vassilevska Better Distance Preservers and Additive Spanners |
| title | Better Distance Preservers and Additive Spanners |
| title_full | Better Distance Preservers and Additive Spanners |
| title_fullStr | Better Distance Preservers and Additive Spanners |
| title_full_unstemmed | Better Distance Preservers and Additive Spanners |
| title_short | Better Distance Preservers and Additive Spanners |
| title_sort | better distance preservers and additive spanners |
| url | https://hdl.handle.net/1721.1/143945 |
| work_keys_str_mv | AT bodwingreg betterdistancepreserversandadditivespanners AT williamsvirginiavassilevska betterdistancepreserversandadditivespanners |