Fully Dynamic Spanners with Worst-Case Update Time

Authors Greg Bodwin, Sebastian Krinninger



PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.17.pdf
  • Filesize: 0.51 MB
  • 18 pages

Document Identifiers

Author Details

Greg Bodwin
Sebastian Krinninger

Cite AsGet BibTex

Greg Bodwin and Sebastian Krinninger. Fully Dynamic Spanners with Worst-Case Update Time. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ESA.2016.17

Abstract

An alpha-spanner of a graph G is a subgraph H such that H preserves all distances of G within a factor of alpha. In this paper, we give fully dynamic algorithms for maintaining a spanner H of a graph G undergoing edge insertions and deletions with worst-case guarantees on the running time after each update. In particular, our algorithms maintain: - a 3-spanner with ~O(n^{1+1/2}) edges with worst-case update time ~O(n^{3/4}), or - a 5-spanner with ~O(n^{1+1/3}) edges with worst-case update time ~O (n^{5/9}). These size/stretch tradeoffs are best possible (up to logarithmic factors). They can be extended to the weighted setting at very minor cost. Our algorithms are randomized and correct with high probability against an oblivious adversary. We also further extend our techniques to construct a 5-spanner with suboptimal size/stretch tradeoff, but improved worst-case update time. To the best of our knowledge, these are the first dynamic spanner algorithms with sublinear worst-case update time guarantees. Since it is known how to maintain a spanner using small amortized}but large worst-case update time [Baswana et al. SODA'08], obtaining algorithms with strong worst-case bounds, as presented in this paper, seems to be the next natural step for this problem.
Keywords
  • Dynamic graph algorithms
  • spanners

Metrics

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

References

  1. Ittai Abraham and Shiri Chechik. Dynamic decremental approximate distance oracles with (1+ε,2) stretch. CoRR, abs/1307.1516, 2013. URL: http://arxiv.org/abs/1307.1516.
  2. Ittai Abraham, Shiri Chechik, and Kunal Talwar. Fully dynamic all-pairs shortest paths: Breaking the o(n) barrier. In International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 1-16, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2014.1.
  3. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. CoRR, abs/1604.02094, 2015. URL: http://arxiv.org/abs/1604.02094.
  4. Amihood Amir, Tsvi Kopelowitz, Avivit Levy, Seth Pettie, Ely Porat, and B. Riva Shalom. Online dictionary matching with one gap. CoRR, abs/1503.07563, 2015. URL: http://arxiv.org/abs/1503.07563.
  5. Giorgio Ausiello, Paolo Giulio Franciosa, and Giuseppe F. Italiano. Small stretch spanners on dynamic graphs. Journal of Graph Algorithms and Applications, 10(2):365-385, 2006. Announced at ESA'05. URL: http://dx.doi.org/10.7155/jgaa.00133.
  6. Baruch Awerbuch. Complexity of network synchronization. Journal of the ACM, 32(4):804-823, 1985. URL: http://dx.doi.org/10.1145/4221.4227.
  7. Leonid Barenboim and Michael Elkin. Distributed Graph Coloring: Fundamentals and Recent Developments, chapter Arbdefective Coloring. Morgan and Claypool, 2013. Google Scholar
  8. Surender Baswana. Streaming algorithm for graph spanners - single pass and constant processing time per edge. Information Processing Letters, 106(3):110-114, 2008. URL: http://dx.doi.org/10.1016/j.ipl.2007.11.001.
  9. Surender Baswana and Telikepalli Kavitha. Faster algorithms for all-pairs approximate shortest paths in undirected graphs. SIAM Journal on Computing, 39(7):2865-2896, 2010. Announced at FOCS'10. URL: http://dx.doi.org/10.1137/080737174.
  10. Surender Baswana, Sumeet Khurana, and Soumojit Sarkar. Fully dynamic randomized algorithms for graph spanners. ACM Transactions on Algorithms, 8(4):35:1-35:51, 2012. Announced at ESA'06, and SODA'08. URL: http://dx.doi.org/10.1145/2344422.2344425.
  11. Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures &Algorithms, 30(4):532-563, 2007. Announced at ICALP'03. URL: http://dx.doi.org/10.1002/rsa.20130.
  12. Shai Ben-David, Allan Borodin, Richard M. Karp, Gábor Tardos, and Avi Wigderson. On the power of randomization in on-line algorithms. Algorithmica, 11(1):2-14, 1994. Announced at STOC'90. URL: http://dx.doi.org/10.1007/BF01294260.
  13. Aaron Bernstein and Liam Roditty. Improved dynamic algorithms for maintaining approximate shortest paths under deletions. In Symposium on Discrete Algorithms (SODA), pages 1355-1365, 2011. URL: http://dx.doi.org/10.1137/1.9781611973082.104.
  14. Shiri Chechik. Approximate distance oracles with constant query time. In Symposium on Theory of Computing (STOC), pages 654-663, 2014. URL: http://dx.doi.org/10.1145/2591796.2591801.
  15. Shiri Chechik. Approximate distance oracles with improved bounds. In Symposium on Theory of Computing (STOC), pages 1-10, 2015. URL: http://dx.doi.org/10.1145/2746539.2746562.
  16. Lenore Cowen. Compact routing with minimum stretch. Journal of Algorithms, 38(1):170-183, 2001. Announced at SODA'99. URL: http://dx.doi.org/10.1006/jagm.2000.1134.
  17. Lenore Cowen and Christopher G. Wagner. Compact roundtrip routing in directed networks. Journal of Algorithms, 50(1):79-95, 2004. Announced at PODC'00. URL: http://dx.doi.org/10.1016/j.jalgor.2003.08.001.
  18. Camil Demetrescu and Giuseppe F. Italiano. A new approach to dynamic all pairs shortest paths. Journal of the ACM, 51(6):968-992, 2004. Announced at STOC'03. URL: http://dx.doi.org/10.1145/1039488.1039492.
  19. Dorit Dor, Shay Halperin, and Uri Zwick. All-pairs almost shortest paths. SIAM Journal on Computing, 29(5):1740-1759, 2000. Announced at FOCS'96. URL: http://dx.doi.org/10.1137/S0097539797327908.
  20. Michael Elkin. Computing almost shortest paths. ACM Transactions on Algorithms, 1(2):283-323, 2005. Announced at PODC'01. URL: http://dx.doi.org/10.1145/1103963.1103968.
  21. Michael Elkin. A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners. In Symposium on Principles of Distributed Computing (PODC), pages 185-194, 2007. URL: http://dx.doi.org/10.1145/1281100.1281128.
  22. Michael Elkin. Streaming and fully dynamic centralized algorithms for constructing and maintaining sparse spanners. ACM Transactions on Algorithms, 7(2):20:1-20:17, 2011. Announced at ICALP'07. URL: http://dx.doi.org/10.1145/1921659.1921666.
  23. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Amnon Nissenzweig. Sparsification - a technique for speeding up dynamic graph algorithms. Journal of the ACM, 44(5):669-696, 1997. Announced at FOCS'92. URL: http://dx.doi.org/10.1145/265910.265914.
  24. Paul Erdős. Extremal problems in graph theory. Theory of graphs and its applications, pages 29-36, 1964. Google Scholar
  25. Arthur M. Farley, Andrzej Proskurowski, Daniel Zappala, and Kurt Windisch. Spanners and message distribution in networks. Discrete Applied Mathematics, 137(2):159-171, 2004. Google Scholar
  26. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, and Jian Zhang. Graph distances in the data-stream model. SIAM Journal on Computing, 38(5):1709-1727, 2008. URL: http://dx.doi.org/10.1137/070683155.
  27. Greg N. Frederickson. Data structures for on-line updating of minimum spanning trees, with applications. SIAM Journal on Computing, 14(4):781-798, 1985. Announced at STOC'83. URL: http://dx.doi.org/10.1137/0214055.
  28. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. Decremental single-source shortest paths on undirected graphs in near-linear total update time. In Symposium on Foundations of Computer Science (FOCS), pages 146-155, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.24.
  29. Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai. A subquadratic-time algorithm for dynamic single-source shortest paths. In Symposium on Discrete Algorithms (SODA), pages 1053-1072, 2014. URL: http://dx.doi.org/10.1137/1.9781611973402.79.
  30. 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, 48(4):723-760, 2001. Announced at STOC'98. URL: http://dx.doi.org/10.1145/502090.502095.
  31. Bruce M. Kapron, Valerie King, and Ben Mountjoy. Dynamic graph connectivity in polylogarithmic worst case time. In Symposium on Discrete Algorithms (SODA), pages 1131-1142, 2013. URL: http://dx.doi.org/10.1137/1.9781611973105.81.
  32. Tsvi Kopelowitz, Robert Krauthgamer, Ely Porat, and Shay Solomon. Orienting fully dynamic graphs with worst-case time bounds. In International Colloquium on Automata, Languages and Programming (ICALP), pages 532-543, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_45.
  33. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Symposium on Theory of Computing (STOC), pages 745-754, 2013. URL: http://dx.doi.org/10.1145/2488608.2488703.
  34. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of Graph Theory, 13(1):99-116, 1989. URL: http://dx.doi.org/10.1002/jgt.3190130114.
  35. David Peleg and Shay Solomon. Dynamic (1 + ε)-approximate matchings: A density-sensitive approach. In Symposium on Discrete Algorithms (SODA), pages 712-729, 2016. URL: http://dx.doi.org/10.1137/1.9781611974331.ch51.
  36. David Peleg and Jeffrey D. Ullman. An optimal synchronizer for the hypercube. SIAM Journal of Computing, 18(4):740-747, 1989. Announced at PODC'87. URL: http://dx.doi.org/10.1137/0218050.
  37. Mihai Pătraşcu and Liam Roditty. Distance oracles beyond the Thorup-Zwick bound. SIAM Journal on Computing, 43(1):300-311, 2014. Announced at FOCS'10. URL: http://dx.doi.org/10.1137/11084128X.
  38. Liam Roditty, Mikkel Thorup, and Uri Zwick. Deterministic constructions of approximate distance oracles and spanners. In International Colloquium on Automata, Languages and Programming (ICALP), pages 261-272, 2005. URL: http://dx.doi.org/10.1007/11523468_22.
  39. Liam Roditty, Mikkel Thorup, and Uri Zwick. Roundtrip spanners and roundtrip routing in directed graphs. ACM Transactions on Algorithms, 4(3), 2008. Announced at SODA'02. URL: http://dx.doi.org/10.1145/1367064.1367069.
  40. Liam Roditty and Uri Zwick. Dynamic approximate all-pairs shortest paths in undirected graphs. SIAM Journal on Computing, 41(3):670-683, 2012. Announced at FOCS'04. URL: http://dx.doi.org/10.1137/090776573.
  41. Piotr Sankowski. Dynamic transitive closure via dynamic matrix inverse. In Symposium on Foundations of Computer Science (FOCS), pages 509-517, 2004. URL: http://dx.doi.org/10.1109/FOCS.2004.25.
  42. Mikkel Thorup. Worst-case update times for fully-dynamic all-pairs shortest paths. In Symposium on Theory of Computing (STOC), pages 112-119, 2005. URL: http://dx.doi.org/10.1145/1060590.1060607.
  43. Mikkel Thorup and Uri Zwick. Compact routing schemes. In Symposium on Parallel Algorithms and Architectures (SPAA), pages 1-10, 2001. URL: http://dx.doi.org/10.1145/378580.378581.
  44. Mikkel Thorup and Uri Zwick. Approximate distance oracles. Journal of the ACM, 52(1):74-92, 2005. Announced at STOC'01. URL: http://dx.doi.org/10.1145/1044731.1044732.
  45. Jeffrey D. Ullman and Mihalis Yannakakis. High-probability parallel transitive-closure algorithms. SIAM Journal on Computing, 20(1):100-125, 1991. Announced at SPAA'90. URL: http://dx.doi.org/10.1137/0220006.
  46. Rephael Wenger. Extremal graphs with no C⁴’s, C⁶’s, or C^10’s. Journal of Combinatorial Theory B, Series B, 52(1):113-116, 1991. URL: http://dx.doi.org/10.1016/0095-8956(91)90097-4.
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