Document Open Access Logo

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

Authors Sayan Bhattacharya, Thatchaphol Saranurak, Pattara Sukprasert

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.17.pdf
  • Filesize: 0.85 MB
  • 19 pages

Document Identifiers

Author Details

Sayan Bhattacharya
  • University of Warwick, Coventry, UK
Thatchaphol Saranurak
  • University of Michigan, Ann Arbor, MI, USA
Pattara Sukprasert
  • Northwestern University, Evanston, IL, USA

Funding

Sayan Bhattacharya is supported by Engineering and Physical Sciences Research Council, UK (EPSRC) Grant EP/S03353X/1.

Cite AsGet BibTex

Sayan Bhattacharya, Thatchaphol Saranurak, and Pattara Sukprasert. Simple Dynamic Spanners with Near-Optimal Recourse Against an Adaptive Adversary. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 17:1-17:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.17

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Sparsification and spanners
Keywords
  • Algorithms
  • Dynamic Algorithms
  • Spanners
  • Recourse

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Amir Abboud, Robert Krauthgamer, and Ohad Trabelsi. Apmf< apsp? gomory-hu tree for unweighted graphs in almost-quadratic time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.02981.
  2. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In FOCS, pages 335-344, 2016. URL: https://doi.org/10.1109/FOCS.2016.44.
  3. Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. In Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 447-455, 2021. Google Scholar
  4. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993. Google Scholar
  5. Giorgio Ausiello, Paolo Giulio Franciosa, and Giuseppe F. Italiano. Small stretch spanners on dynamic graphs. J. Graph Algorithms Appl., 10(2):365-385, 2006. Announced at ESA'05. URL: https://doi.org/10.7155/jgaa.00133.
  6. Chen Avin, Marcin Bienkowski, Andreas Loukas, Maciej Pacut, and Stefan Schmid. Dynamic balanced graph partitioning. SIAM Journal on Discrete Mathematics, 34(3):1791-1812, 2020. Google Scholar
  7. Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput., 50(3), 2021. URL: https://doi.org/10.1137/16M1103646.
  8. Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Trans. Algorithms, 8(4):35:1-35:51, 2012. Announced at SODA'08. URL: https://doi.org/10.1145/2344422.2344425.
  9. Soheil Behnezhad, Mahsa Derakhshan, MohammadTaghi Hajiaghayi, Cliff Stein, and Madhu Sudan. Fully dynamic maximal independent set with polylogarithmic update time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 382-405, 2019. URL: https://doi.org/10.1109/FOCS.2019.00032.
  10. Omri Ben-Eliezer, Rajesh Jayaram, David P Woodruff, and Eylon Yogev. A framework for adversarially robust streaming algorithms. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI symposium on principles of database systems, pages 63-80, 2020. Google Scholar
  11. Aaron Bernstein. Deterministic partially dynamic single source shortest paths in weighted graphs. In ICALP, volume 80, pages 44:1-44:14, 2017. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.44.
  12. Aaron Bernstein, Jan van den Brand, Maximilian Probst Gutenberg, Danupon Nanongkai, Thatchaphol Saranurak, Aaron Sidford, and He Sun. Fully-dynamic graph sparsifiers against an adaptive adversary. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.08432.
  13. Aaron Bernstein and Shiri Chechik. Deterministic decremental single source shortest paths: beyond the o(mn) bound. In STOC, pages 389-397, 2016. Google Scholar
  14. Aaron Bernstein and Shiri Chechik. Deterministic partially dynamic single source shortest paths for sparse graphs. In SODA, pages 453-469, 2017. Google Scholar
  15. Aaron Bernstein and Shiri Chechik. Incremental topological sort and cycle detection in expected total time. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 21-34, 2018. URL: https://doi.org/10.1137/1.9781611975031.2.
  16. Aaron Bernstein, Sebastian Forster, and Monika Henzinger. A deamortization approach for dynamic spanner and dynamic maximal matching. In SODA, pages 1899-1918, 2019. Google Scholar
  17. Aaron Bernstein, Maximilian Probst Gutenberg, and Thatchaphol Saranurak. Deterministic decremental sssp and approximate min-cost flow in almost-linear time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.07149.
  18. Aaron Bernstein, Maximilian Probst, and Christian Wulff-Nilsen. Decremental strongly-connected components and single-source reachability in near-linear time. In STOC, pages 365-376, 2019. Google Scholar
  19. Sayan Bhattacharya, Fabrizio Grandoni, and David Wajc. Online edge coloring algorithms via the nibble method. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2830-2842. SIAM, 2021. Google Scholar
  20. Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano. Deterministic fully dynamic data structures for vertex cover and matching. In SODA, 2015. Google Scholar
  21. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. New deterministic approximation algorithms for fully dynamic matching. In STOC, pages 398-411, 2016. Google Scholar
  22. Sayan Bhattacharya, Monika Henzinger, and Danupon Nanongkai. Fully dynamic approximate maximum matching and minimum vertex cover in O(log^3 n) worst case update time. In SODA, pages 470-489, 2017. Google Scholar
  23. Sayan Bhattacharya and Peter Kiss. Deterministic rounding of dynamic fractional matchings. arXiv preprint, 2021. URL: http://arxiv.org/abs/2105.01615.
  24. Sayan Bhattacharya and Janardhan Kulkarni. Deterministically maintaining a (2 +ε)-approximate minimum vertex cover in o(1/ε²) amortized update time. In SODA, 2019. Google Scholar
  25. Greg Bodwin and Sebastian Krinninger. Fully dynamic spanners with worst-case update time. In ESA, pages 17:1-17:18, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.17.
  26. Jan van den Brand, Yin Tat Lee, Yang P. Liu, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Minimum cost flows, mdps, and l1-regression in nearly linear time for dense instances. In STOC, pages 859-869. ACM, 2021. Google Scholar
  27. Jan van den Brand, Yin Tat Lee, Danupon Nanongkai, Richard Peng, Thatchaphol Saranurak, Aaron Sidford, Zhao Song, and Di Wang. Bipartite matching in nearly-linear time on moderately dense graphs. In FOCS, pages 919-930. IEEE, 2020. Google Scholar
  28. Vladimir Braverman, Avinatan Hassidim, Yossi Matias, Mariano Schain, Sandeep Silwal, and Samson Zhou. Adversarial robustness of streaming algorithms through importance sampling. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.14952.
  29. Keren Censor-Hillel, Elad Haramaty, and Zohar S. Karnin. Optimal dynamic distributed MIS. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, PODC 2016, Chicago, IL, USA, July 25-28, 2016, pages 217-226, 2016. URL: https://doi.org/10.1145/2933057.2933083.
  30. Shiri Chechik and Tianyi Zhang. Fully dynamic maximal independent set in expected poly-log update time. In 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 370-381, 2019. URL: https://doi.org/10.1109/FOCS.2019.00031.
  31. Shiri Chechik and Tianyi Zhang. Dynamic low-stretch spanning trees in subpolynomial time. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 463-475. SIAM, 2020. Google Scholar
  32. Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1135-1146. IEEE, 2020. Google Scholar
  33. Julia Chuzhoy. Decremental all-pairs shortest paths in deterministic near-linear time. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 626-639, 2021. URL: https://doi.org/10.1145/3406325.3451025.
  34. Julia Chuzhoy, Yu Gao, Jason Li, Danupon Nanongkai, Richard Peng, and Thatchaphol Saranurak. A deterministic algorithm for balanced cut with applications to dynamic connectivity, flows, and beyond. CoRR, abs/1910.08025, 2019. Google Scholar
  35. Julia Chuzhoy and Sanjeev Khanna. A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems. In STOC, pages 389-400, 2019. Google Scholar
  36. Julia Chuzhoy and Thatchaphol Saranurak. Deterministic algorithms for decremental shortest paths via layered core decomposition. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2478-2496. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.147.
  37. Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Leon Roth. Preserving statistical validity in adaptive data analysis. In Proceedings of the forty-seventh annual ACM symposium on Theory of computing, pages 117-126, 2015. Google Scholar
  38. Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Trans. Algorithms, 7(2):20:1-20:17, 2011. Announced at ICALP'07. URL: https://doi.org/10.1145/1921659.1921666.
  39. Lisa Fleischer. Approximating fractional multicommodity flow independent of the number of commodities. SIAM J. Discrete Math., 13(4):505-520, 2000. announced at FOCS'99. URL: https://doi.org/10.1137/S0895480199355754.
  40. Sebastian Forster and Gramoz Goranci. Dynamic low-stretch trees via dynamic low-diameter decompositions. In STOC, pages 377-388. ACM, 2019. Google Scholar
  41. Naveen Garg and Jochen Könemann. Faster and simpler algorithms for multicommodity flow and other fractional packing problems. SIAM J. Comput., 37(2):630-652, 2007. URL: https://doi.org/10.1137/S0097539704446232.
  42. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 2212-2228. SIAM, 2021. URL: https://doi.org/10.1137/1.9781611976465.132.
  43. Ofer Grossman and Merav Parter. Improved deterministic distributed construction of spanners. In DISC, pages 24:1-24:16, 2017. URL: https://doi.org/10.4230/LIPIcs.DISC.2017.24.
  44. Anupam Gupta and Amit Kumar. Online steiner tree with deletions. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 455-467. SIAM, 2014. Google Scholar
  45. Anupam Gupta, Amit Kumar, and Cliff Stein. Maintaining assignments online: Matching, scheduling, and flows. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 468-479. SIAM, 2014. Google Scholar
  46. Anupam Gupta and Roie Levin. Fully-dynamic submodular cover with bounded recourse. In 2020 IEEE 61st Annual Symposium on Foundations of Computer Science (FOCS), pages 1147-1157. IEEE, 2020. Google Scholar
  47. Varun Gupta, Christopher Jung, Seth Neel, Aaron Roth, Saeed Sharifi-Malvajerdi, and Chris Waites. Adaptive machine unlearning. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.04378.
  48. Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. New algorithms and hardness for incremental single-source shortest paths in directed graphs. In Symposium on Theory of Computing, 2020. URL: http://arxiv.org/abs/2001.10751.
  49. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Decremental SSSP in weighted digraphs: Faster and against an adaptive adversary. In SODA, pages 2542-2561, 2020. Google Scholar
  50. Maximilian Probst Gutenberg and Christian Wulff-Nilsen. Deterministic algorithms for decremental approximate shortest paths: Faster and simpler. In SODA, pages 2522-2541, 2020. Google Scholar
  51. Moritz Hardt and Jonathan Ullman. Preventing false discovery in interactive data analysis is hard. In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 454-463. IEEE, 2014. Google Scholar
  52. Avinatan Hasidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. Adversarially robust streaming algorithms via differential privacy. Advances in Neural Information Processing Systems, 33, 2020. Google Scholar
  53. Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723-760, 2001. Google Scholar
  54. Jacob Holm and Eva Rotenberg. Fully-dynamic planarity testing in polylogarithmic time. In STOC, pages 167-180. ACM, 2020. Google Scholar
  55. Jacob Holm and Eva Rotenberg. Worst-case polylog incremental spqr-trees: Embeddings, planarity, and triconnectivity. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020, Salt Lake City, UT, USA, January 5-8, 2020, pages 2378-2397, 2020. URL: https://doi.org/10.1137/1.9781611975994.146.
  56. Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating adaptive streaming from oblivious streaming. arXiv preprint, 2021. URL: http://arxiv.org/abs/2101.10836.
  57. Jason Li. Deterministic mincut in almost-linear time. In STOC, pages 384-395. ACM, 2021. Google Scholar
  58. Jason Li, Debmalya Panigrahi, and Thatchaphol Saranurak. A nearly optimal all-pairs min-cuts algorithm in simple graphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.02233.
  59. Jason Li and Thatchaphol Saranurak. Deterministic weighted expander decomposition in almost-linear time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.01567.
  60. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic spanning forest with worst-case update time: adaptive, Las vegas, and O(n^1/2-ε)-time. In STOC, pages 1122-1129, 2017. URL: https://doi.org/10.1145/3055399.3055447.
  61. Danupon Nanongkai, Thatchaphol Saranurak, and Christian Wulff-Nilsen. Dynamic minimum spanning forest with subpolynomial worst-case update time. In FOCS, pages 950-961, 2017. Google Scholar
  62. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In SODA, pages 2616-2635, 2019. Google Scholar
  63. Thomas Steinke and Jonathan Ullman. Tight lower bounds for differentially private selection. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 552-563. IEEE, 2017. Google Scholar
  64. David Wajc. Rounding dynamic matchings against an adaptive adversary. Symposium on Theory of Computing, 2020. URL: http://arxiv.org/abs/1911.05545.
  65. Rephael Wenger. Extremal graphs with no c4’s, c6’s, or c10’s. Journal of Combinatorial Theory, Series B, 52(1):113-116, 1991. Google Scholar
  66. David P Woodruff and Samson Zhou. Tight bounds for adversarially robust streams and sliding windows via difference estimators. arXiv preprint, 2020. URL: http://arxiv.org/abs/2011.07471.
  67. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In STOC, pages 1130-1143, 2017. URL: https://doi.org/10.1145/3055399.3055415.
  68. Tianyi Zhang. Faster cut-equivalent trees in simple graphs. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.03305.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact