Document Open Access Logo

The Power of Vertex Sparsifiers in Dynamic Graph Algorithms

Authors Gramoz Goranci, Monika Henzinger, Pan Peng

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.45.pdf
  • Filesize: 0.49 MB
  • 14 pages

Document Identifiers

Author Details

Gramoz Goranci
Monika Henzinger
Pan Peng

Cite As Get BibTex

Gramoz Goranci, Monika Henzinger, and Pan Peng. The Power of Vertex Sparsifiers in Dynamic Graph Algorithms. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 45:1-45:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.45

Abstract

We introduce a new algorithmic framework for designing dynamic graph algorithms in minor-free graphs, by exploiting the structure of such graphs and a tool called vertex sparsification, which is a way to compress large graphs into small ones that well preserve relevant properties among a subset of vertices and has previously mainly been used in the design of approximation algorithms. 

Using this framework, we obtain a Monte Carlo randomized fully dynamic algorithm for (1 + epsilon)-approximating the energy of electrical flows in n-vertex planar graphs with tilde{O}(r epsilon^{-2}) worst-case update time and tilde{O}((r + n / sqrt{r}) epsilon^{-2}) worst-case query time, for any r larger than some constant. For r=n^{2/3}, this gives tilde{O}(n^{2/3} epsilon^{-2}) update time and tilde{O}(n^{2/3} epsilon^{-2}) query time. We also extend this algorithm to work for minor-free graphs with similar approximation and running time guarantees. Furthermore, we illustrate our framework on the all-pairs max flow and shortest path problems by giving corresponding dynamic algorithms in minor-free graphs with both sublinear update and query times. To the best of our knowledge, our results are the first to systematically establish such a connection between dynamic graph algorithms and vertex sparsification. 

We also present both upper bound and lower bound for maintaining the energy of electrical flows in the incremental subgraph model, where updates consist of only vertex activations, which might be of independent interest.

Subject Classification

Keywords
  • Dynamic graph algorithms
  • electrical flow
  • minor-free graphs
  • max flow

Metrics

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

References

  1. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In Proc. of the 57th FOCS, pages 477-486, 2016. Google Scholar
  2. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. of the 55th FOCS, pages 434-443, 2014. Google Scholar
  3. Ittai Abraham, Shiri Chechik, and Cyril Gavoille. Fully dynamic approximate distance oracles for planar graphs via forbidden-set distance labels. In Proc. of the 44th STOC, pages 1199-1218, 2012. Google Scholar
  4. Ittai Abraham, Shiri Chechik, and Kunal Talwar. Fully dynamic all-pairs shortest paths: Breaking the o(n) barrier. In Proc. of the 17th APPROX, 2014. Google Scholar
  5. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In Proc. of the 57th FOCS, pages 335-344, 2016. Google Scholar
  6. Noga Alon and Raphael Yuster. Solving linear systems through nested dissection. In Proc. of the 51st FOCS, pages 225-234, 2010. Google Scholar
  7. Alexandr Andoni, Anupam Gupta, and Robert Krauthgamer. Towards (1+ ε)-approximate flow sparsifiers. In Proc. of the 25th SODA, pages 279-293, 2014. Google Scholar
  8. Sanjeev Arora, Elad Hazan, and Satyen Kale. The multiplicative weights update method: a meta-algorithm and applications. Theory of Computing, 8(1):121-164, 2012. Google Scholar
  9. Aaron Bernstein. Fully dynamic (2+ε) approximate all-pairs shortest paths with fast query and close to linear update time. In Proc. of the 50th FOCS, pages 693-702, 2009. Google Scholar
  10. Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Proc. of the 43rd STOC, pages 273-282, 2011. Google Scholar
  11. Julia Chuzhoy. Routing in undirected graphs with constant congestion. In Proc. of the 44th STOC, pages 855-874. ACM, 2012. Google Scholar
  12. Peter G Doyle and J Laurie Snell. Random Walks and Electric Networks. Carus Mathematical Monographs. Mathematical Association of America, 1984. Google Scholar
  13. David Durfee, Rasmus Kyng, John Peebles, Anup B. Rao, and Sushant Sachdeva. Sampling random spanning trees faster than matrix multiplication. In Proc. of the 49th STOC, pages 730-742, 2017. Google Scholar
  14. David Eppstein, Zvi Galil, Giuseppe F. Italiano, and Thomas H. Spencer. Separator based sparsification. i. planary testing and minimum spanning trees. J. Comput. Syst. Sci., 52(1):3-27, 1996. Google Scholar
  15. Greg N Federickson. Fast algorithms for shortest paths in planar graphs, with applications. SIAM Journal on Computing, 16(6):1004-1022, 1987. Google Scholar
  16. Zvi Galil, Giuseppe F. Italiano, and Neil Sarnak. Fully dynamic planarity testing with applications. J. ACM, 46(1):28-91, 1999. Google Scholar
  17. MT Goodrich. Planar separators and parallel polygon triangulation. Journal of Computer and System Sciences, 3(51):374-389, 1995. Google Scholar
  18. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. of the 47th STOC, pages 21-30, 2015. Google Scholar
  19. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Proc. of the 43rd STOC, pages 313-322, 2011. Google Scholar
  20. Michael Kapralov, Yin Tat Lee, Cameron Musco, Christopher Musco, and Aaron Sidford. Single pass spectral sparsification in dynamic streams. In Proc. of the 55th FOCS, pages 561-570, 2014. Google Scholar
  21. Ken-ichi Kawarabayashi and Bruce Reed. A separator theorem in minor-closed classes. In Proc. of the 51st FOCS, pages 153-162. IEEE, 2010. Google Scholar
  22. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Proc. of the 25th SODA, pages 217-226, 2014. Google Scholar
  23. Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting. Theory Comput. Syst., 53(2):243-262, 2013. Google Scholar
  24. Richard Kenyon. The laplacian on planar graphs and graphs on surfaces. Current Developments in Mathematics, 2011. Google Scholar
  25. Philip N Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In Proc. of the 45th STOC, pages 505-514, 2013. Google Scholar
  26. Philip N. Klein and Sairam Subramanian. A fully dynamic approximation scheme for shortest paths in planar graphs. Algorithmica, 22(3):235-249, 1998. Google Scholar
  27. Ioannis Koutis and Gary L. Miller. A linear work, o(n^1/6) time, parallel algorithm for solving planar laplacians. In Proc. of the 18th SODA, pages 1002-1011, 2007. Google Scholar
  28. Ioannis Koutis, Gary L. Miller, and Richard Peng. Approaching optimality for solving SDD linear systems. SIAM J. Comput., 43(1):337-354, 2014. Google Scholar
  29. Robert Krauthgamer, Huy L Nguyen, and Tamar Zondiner. Preserving terminal distances using minors. SIAM Journal on Discrete Mathematics, 28(1):127-141, 2014. Google Scholar
  30. Rasmus Kyng and Sushant Sachdeva. Approximate gaussian elimination for laplacians-fast, sparse, and simple. In Proc. of the 57th FOCS, pages 573-582, 2016. Google Scholar
  31. Yin Tat Lee, Satish Rao, and Nikhil Srivastava. A new approach to computing maximum flows using electrical flows. In Proc. of the 45th STOC, pages 755-764, 2013. Google Scholar
  32. Richard J. Lipton, Donald J. Rose, and Robert Endre Tarjan. Generalized nested dissection. SIAM Journal on Numerical Analysis, 16(2):346-358, 1979. Google Scholar
  33. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Proc. of the 54th FOCS, pages 253-262, 2013. Google Scholar
  34. Aleksander Madry. Computing maximum flow with augmenting electrical flows. In Proc. of the 57th FOCS, pages 593-602, 2016. Google Scholar
  35. Gary L. Miller and Richard Peng. Approximate maximum flow on separable undirected graphs. In Proc. of the 24th SODA, pages 1151-1170, 2013. Google Scholar
  36. Ankur Moitra. Approximation algorithms for multicommodity-type problems with guarantees independent of the graph size. In Proc. of the 50th FOCS, pages 3-12, 2009. Google Scholar
  37. Richard Peng. Approximate undirected maximum flows in O(mpolylog(n)) time. In Proc. of the 27th SODA, pages 1862-1867, 2016. Google Scholar
  38. Daniel A. Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM J. Comput., 40(6):1913-1926, 2011. Google Scholar
  39. Daniel A. Spielman and Shang-Hua Teng. Spectral sparsification of graphs. SIAM J. Comput., 40(4):981-1025, 2011. Google Scholar
  40. Daniel A. Spielman and Shang-Hua Teng. Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems. SIAM J. Matrix Analysis Applications, 35(3):835-885, 2014. Google Scholar
  41. Sairam Subramanian. A fully dynamic data structure for reachability in planar digraphs. In Proc. of the 1st ESA, pages 372-383, 1993. Google Scholar
  42. Virginia Vassilevska Williams. Multiplying matrices faster than coppersmith-winograd. In Proc. of the 44th STOC, pages 887-898, 2012. Google Scholar
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 About DROPS Imprint Privacy Contact