{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T09:20:41Z","timestamp":1787390441878,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Let $G = (V,E)$ be an undirected unweighted graph on $n$ vertices. A subgraph $H$ of $G$ is called a purely additive spanner of $G$ with stretch $\\beta$ if for each $(u,v) \\in V \\times V$, the $u$-$v$ distance in $H$ is at most $\\delta_G(u,v) + \\beta$. We currently know sparse purely additive spanners with $\\beta = O(1)$ only for $\\beta = 2,4,6$. When $\\beta = 2$, the size of the spanner is $O(n^{3\/2})$; when $\\beta = 4$, the size of the spanner is $O(n^{1.4}\\log^{0.2}n)$; and when $\\beta = 6$, the size of the spanner is $O(n^{4\/3})$. The following is a natural relaxation of the above problem: we care for only certain distances, these are captured by the set $\\mathcal{P} \\subseteq V \\times V$, and the problem is to construct a sparse subgraph $H$ (also called a $\\mathcal{P}$-spanner), where for every $(u,v) \\in \\mathcal{P}$, the $u$-$v$ distance in $H$ is at most $\\delta_G(u,v) + \\beta$. In this paper we show algorithms to construct the following for $\\beta = 2$: a $\\mathcal{P}$-spanner of size $\\tilde{O}(n|\\mathcal{P}|^{1\/3})$ for any $\\mathcal{P}\\subseteq V\\times V$ and a $\\mathcal{P}$-spanner of size $\\tilde{O}(n|\\mathcal{P}|^{1\/4})$ when $\\mathcal{P} = S \\times V$, where $S \\subseteq V$. Our $\\mathcal{P}$-spanner with additive stretch 2 leads to a simple deterministic construction of a purely additive spanner with stretch 4 and size $O(n^{1.4}\\log^{0.2}n)$. We also consider a variant of the $\\mathcal{P}$-spanner problem where the set $\\mathcal{P}$ is implicitly given via a distance threshold $D$. That is, $\\mathcal{P} = \\{(u,v): \\delta_G(u,v) \\ge D\\}$. We refer to such a $\\mathcal{P}$-spanner as an approximate $D$-preserver. A $D$-preserver is a subgraph where distances $\\ge D$ are exactly preserved and $D$-preservers of size $O(n^2\/D)$ are known. For a given $D \\in \\mathbb{Z}^+$ and any integer $k \\ge 1$, we construct an $\\tilde{O}(n^{3\/2}\/D^{k\/(2k+2)})$-sized subgraph where distances $\\ge D$ are approximated with an additive stretch of $4k$. In particular, when $k = \\lfloor\\log D\\rfloor$, this subgraph has size $\\tilde{O}(n\\cdot\\sqrt{n\/D})$.<\/jats:p>","DOI":"10.1137\/140953927","type":"journal-article","created":{"date-parts":[[2015,11,10]],"date-time":"2015-11-10T12:11:47Z","timestamp":1447157507000},"page":"2239-2254","source":"Crossref","is-referenced-by-count":11,"title":["Small Stretch Pairwise Spanners and Approximate $D$-Preservers"],"prefix":"10.1137","volume":"29","author":[{"given":"Telikepalli","family":"Kavitha","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nithin M.","family":"Varma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,11,10]]},"reference":[{"key":"atypb1","first-page":"1167","volume":"28","author":"Aingworth D.","year":"1999","journal-title":"Comput."},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794271898"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1137\/0405013"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/080737174"},{"key":"atypb5","first-page":"7","author":"Baswana S.","year":"2010","journal-title":"ACM Trans. Algorithms"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20130"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198518"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480103431046"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"S. Chechik,\n                      New additive spanners\n                      , in Proceedings of the 24th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013, pp. 498-512.","DOI":"10.1137\/1.9781611973105.36"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.4.3.233"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"E. Cohen,\n                      Fast algorithms for constructing $t$-spanners and paths of stretch\n                      $t$, in Proceedings of the 34th IEEE Symposium on Foundations of Computer Science (FOCS), 1993, pp. 648-658.","DOI":"10.1109\/SFCS.1993.366822"},{"key":"atypb12","unstructured":"D. Coppersmith and M. Elkin,\n                      Sparse source-wise and pair-wise distance preservers\n                      , in Proceedings of the 16th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 660-669."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1134"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.08.001"},{"key":"atypb15","unstructured":"M. Cygan, F. Grandoni, and T. Kavitha,\n                      On pairwise spanners\n                      , in Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science (STACS), 2013, pp. 209-220."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797327908"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/1103963.1103968"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701393384"},{"key":"atypb19","unstructured":"C. Gavoille, D. Peleg, S. Perennes, and R. Raz,\n                      Distance labeling in graphs\n                      , in Proceedings of the 12th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2001, pp. 210-219."},{"key":"atypb20","unstructured":"S. Halperin and U. Zwick,\n                      Linear time deterministic algorithm for computing spanners for unweighted graphs\n                      , unpublished result, 1996."},{"key":"atypb21","unstructured":"T. Kavitha,\n                      New pairwise spanners\n                      , in Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science (STACS), 2015, pp. 513-526."},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"T. Kavitha and N. M. Varma,\n                      Small stretch pairwise spanners\n                      , in Proceedings of the 40th International Colloquium on Automata, Languages and Programming (ICALP), 2013, pp. 601-612.","DOI":"10.1007\/978-3-642-39206-1_51"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"M. B. T. Knudsen,\n                      Additive spanners: A simple construction\n                      , in Proceedings of the 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 2014, pp. 277-281.","DOI":"10.1007\/978-3-319-08404-6_24"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(75)90058-8"},{"key":"atypb25","doi-asserted-by":"crossref","unstructured":"M. Parter, \\newblock\n                      Bypassing Erdo\u0308s' girth conjecture: Hybrid spanners and sourcewise spanners\n                      , \\newblock in Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP), 2014, pp. 608-619.","DOI":"10.1007\/978-3-662-43951-7_49"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(200003)33:3<167::AID-JGT7>3.0.CO;2-5"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1137\/0218050"},{"key":"atypb29","first-page":"6","author":"Pettie S.","year":"2009","journal-title":"ACM Trans. Algorithms"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1007\/BF02020254"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"L. Roditty and U. Zwick,\n                      On dynamic shortest paths problems\n                      , in Proceedings of the 12th Annual European Symposium on Algorithms (ESA), 2004, pp. 580-591.","DOI":"10.1007\/978-3-540-30140-0_52"},{"key":"atypb32","doi-asserted-by":"crossref","unstructured":"L. Roditty, M. Thorup, and U. Zwick,\n                      Deterministic constructions of approximate distance oracles and spanners\n                      , in Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP), 2005, pp. 261-272.","DOI":"10.1007\/11523468_22"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"atypb34","doi-asserted-by":"crossref","unstructured":"M. Thorup and U. Zwick,\n                      Spanners and emulators with sublinear distance errors\n                      , in Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006, pp. 802-809.","DOI":"10.1145\/1109557.1109645"},{"key":"atypb35","doi-asserted-by":"crossref","unstructured":"D. P. Woodruff,\n                      Lower bounds for additive spanners, emulators, and more\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2006, pp. 389-398.","DOI":"10.1109\/FOCS.2006.45"},{"key":"atypb36","doi-asserted-by":"crossref","unstructured":"D. P. Woodruff,\n                      Additive spanners in nearly quadratic time\n                      , in Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), 2010, pp. 463-474.","DOI":"10.1007\/978-3-642-14165-2_40"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140953927","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:47:32Z","timestamp":1787320052000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140953927"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140953927"],"URL":"https:\/\/doi.org\/10.1137\/140953927","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}