Document Open Access Logo

On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter

Author Søren Dahlgaard

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.48.pdf
  • Filesize: 483 kB
  • 14 pages

Document Identifiers

Author Details

Søren Dahlgaard

Cite As Get BibTex

Søren Dahlgaard. On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 48:1-48:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ICALP.2016.48

Abstract

Conditional lower bounds for dynamic graph problems has received a great deal of attention in recent years. While many results are now known for the fully-dynamic case and such bounds often imply worst-case bounds for the partially dynamic setting, it seems much more difficult to prove amortized bounds for incremental and decremental algorithms. In this paper we consider partially dynamic versions of three classic problems in graph theory. Based on popular conjectures we show that:

- No algorithm with amortized update time O(n^{1-epsilon}) exists for incremental or decremental maximum cardinality bipartite matching. This significantly improves on the O(m^{1/2-epsilon}) bound for sparse graphs of Henzinger et al. [STOC'15] and O(n^{1/3-epsilon}) bound of Kopelowitz, Pettie and Porat. Our linear bound also appears more natural. In addition, the result we present separates the node-addition model from the edge insertion model, as an algorithm with total update time O(m*sqrt(n)) exists for the former by Bosek et al. [FOCS'14].

- No algorithm with amortized update time O(m^{1-epsilon}) exists for incremental or decremental maximum flow in directed and weighted sparse graphs. No such lower bound was known for partially dynamic maximum flow previously. Furthermore no algorithm with amortized update time O(n^{1-epsilon}) exists for directed and unweighted graphs or undirected and weighted graphs.

- No algorithm with amortized update time O(n^{1/2-epsilon}) exists for incremental or decremental (4/3 - epsilon')-approximating the diameter of an unweighted graph. We also show a slightly stronger bound if node additions are allowed. The result is then extended to the static case, where we show that no O((n*sqrt(m))^{1-epsilon}) algorithm exists. We also extend the result to the case when an additive error is allowed in the approximation. While our bounds are weaker than the already known bounds of Roditty and Vassilevska Williams [STOC'13], it is based on a weaker conjecture of Abboud et al. [STOC'15] and is the first known reduction from the 3SUM and APSP problems to diameter. Showing an equivalence between APSP and diameter is a major open problem in this area (Abboud et al. [SODA'15]), and thus showing even a weak connection in this direction is of interest.

Subject Classification

Keywords
  • Conditional lower bounds
  • Maximum cardinality matching
  • Diameter in graphs
  • Hardness in P
  • Partially dynamic problems
  • Maximum flow

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. If the current clique algorithms are optimal, so is valiant’s parser. In Proc. 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 98-117, 2015. Google Scholar
  2. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proc. 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 59-78, 2015. Google Scholar
  3. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In Proc. 26th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 1681-1697, 2015. Google Scholar
  4. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends or: A polylog shaved is a lower bound made. In Proc. 48th ACM Symposium on Theory of Computing (STOC), 2016. To appear. Google Scholar
  5. Amir Abboud and Kevin Lewi. Exact weight subgraphs and the k-sum conjecture. In Proc. 40th International Colloquium on Automata, Languages and Programming (ICALP), pages 1-12, 2013. Google Scholar
  6. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS), pages 434-443, 2014. Google Scholar
  7. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proc. 41st International Colloquium on Automata, Languages and Programming (ICALP), pages 39-51, 2014. Google Scholar
  8. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In Proc. 47th ACM Symposium on Theory of Computing (STOC), pages 41-50, 2015. Google Scholar
  9. Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. Fast estimation of diameter and shortest paths (without matrix multiplication). SIAM Journal on Computing, 28(4):1167-1181, 1999. Google Scholar
  10. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proc. 47th ACM Symposium on Theory of Computing (STOC), pages 51-58, 2015. Google Scholar
  11. Bartlomiej Bosek, Dariusz Leniowski, Piotr Sankowski, and Anna Zych. Online bipartite matching in offline time. In Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS), pages 384-393, 2014. Google Scholar
  12. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proc. 56th IEEE Symposium on Foundations of Computer Science (FOCS), pages 79-97, 2015. Google Scholar
  13. Massimo Cairo, Roberto Grossi, and Romeo Rizzi. New bounds for approximating extremal distances in undirected graphs. In Proc. 27th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 363-376, 2016. Google Scholar
  14. Shiri Chechik, Daniel H. Larkin, Liam Roditty, Grant Schoenebeck, Robert Endre Tarjan, and Virginia Vassilevska Williams. Better approximation algorithms for the graph diameter. In Proc. 25th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 1041-1052, 2014. Google Scholar
  15. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  16. Marek Cygan, Harold N. Gabow, and Piotr Sankowski. Algorithmic applications of baur-strassen’s theorem: Shortest cycles, diameter, and matchings. Journal of the ACM, 62(4):28, 2015. Google Scholar
  17. 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. 47th ACM Symposium on Theory of Computing (STOC), pages 21-30, 2015. Google Scholar
  18. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001. Google Scholar
  19. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512-530, 2001. Google Scholar
  20. 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. 25th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 217-226, 2014. Google Scholar
  21. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In Proc. 27th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 1272-1287, 2016. Google Scholar
  22. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in õ(vrank) iterations and faster algorithms for maximum flow. In Proc. 55th IEEE Symposium on Foundations of Computer Science (FOCS), pages 424-433, 2014. Google Scholar
  23. Aleksander Madry. From Graphs to Matrices, and Back: New Techniques for Graph Algorithms. PhD thesis, Massachusetts Institute of Technology, 6 2011. Google Scholar
  24. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Proc. 54th IEEE Symposium on Foundations of Computer Science (FOCS), pages 253-262, 2013. Google Scholar
  25. Ofer Neiman and Shay Solomon. Simple deterministic algorithms for fully dynamic maximal matching. In Proc. 45th ACM Symposium on Theory of Computing (STOC), pages 745-754, 2013. Google Scholar
  26. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In Proc. 42nd ACM Symposium on Theory of Computing (STOC), pages 603-610, 2010. Google Scholar
  27. Mihai Pǎtraşcu and Ryan Williams. On the possibility of faster SAT algorithms. In Proc. 21st ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 1065-1075, 2010. Google Scholar
  28. Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. In Proc. 45th ACM Symposium on Theory of Computing (STOC), pages 515-524, 2013. Google Scholar
  29. Liam Roditty and Uri Zwick. On dynamic shortest paths problems. Algorithmica, 61(2):389-401, 2011. See also ESA'04. Google Scholar
  30. Piotr Sankowski. Faster dynamic matchings and vertex connectivity. In Proc. 18th ACM/SIAM Symposium on Discrete Algorithms (SODA), pages 118-126, 2007. Google Scholar
  31. Jonah Sherman. Nearly maximum flows in nearly linear time. In Proc. 54th IEEE Symposium on Foundations of Computer Science (FOCS), pages 263-269, 2013. Google Scholar
  32. Virginia Vassilevska and Ryan Williams. Finding, minimizing, and counting weighted subgraphs. In Proc. 41st ACM Symposium on Theory of Computing (STOC), pages 455-464, 2009. 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