License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.17
URN: urn:nbn:de:0030-drops-169555
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16955/
Go to the corresponding LIPIcs Volume Portal

Bhattacharya, Sayan ; Saranurak, Thatchaphol ; Sukprasert, Pattara

Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary

pdf-format:
LIPIcs-ESA-2022-17.pdf (0.9 MB)

Abstract

Designing dynamic algorithms against an adaptive adversary whose performance match the ones assuming an oblivious adversary is a major research program in the field of dynamic graph algorithms. One of the prominent examples whose oblivious-vs-adaptive gap remains maximally large is the fully dynamic spanner problem; there exist algorithms assuming an oblivious adversary with near-optimal size-stretch trade-off using only polylog(n) update time [Baswana, Khurana, and Sarkar TALG'12; Forster and Goranci STOC'19; Bernstein, Forster, and Henzinger SODA'20], while against an adaptive adversary, even when we allow infinite time and only count recourse (i.e. the number of edge changes per update in the maintained spanner), all previous algorithms with stretch at most log⁵(n) require at least Ω(n) amortized recourse [Ausiello, Franciosa, and Italiano ESA'05].
In this paper, we completely close this gap with respect to recourse by showing algorithms against an adaptive adversary with near-optimal size-stretch trade-off and recourse. More precisely, for any k ≥ 1, our algorithm maintains a (2k-1)-spanner of size O(n^{1+1/k}log n) with O(log n) amortized recourse, which is optimal in all parameters up to a O(log n) factor. As a step toward algorithms with small update time (not just recourse), we show another algorithm that maintains a 3-spanner of size Õ(n^{1.5}) with polylog(n) amortized recourse and simultaneously Õ(√n) worst-case update time.

BibTeX - Entry

@InProceedings{bhattacharya_et_al:LIPIcs.ESA.2022.17,
  author =	{Bhattacharya, Sayan and Saranurak, Thatchaphol and Sukprasert, Pattara},
  title =	{{Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{17:1--17:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16955},
  URN =		{urn:nbn:de:0030-drops-169555},
  doi =		{10.4230/LIPIcs.ESA.2022.17},
  annote =	{Keywords: Algorithms, Dynamic Algorithms, Spanners, Recourse}
}

Keywords: Algorithms, Dynamic Algorithms, Spanners, Recourse
Collection: 30th Annual European Symposium on Algorithms (ESA 2022)
Issue Date: 2022
Date of publication: 01.09.2022

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI