Document Open Access Logo

Conditional Hardness for Sensitivity Problems

Authors Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2017.26.pdf
  • Filesize: 0.7 MB
  • 31 pages

Document Identifiers

Author Details

Monika Henzinger
Andrea Lincoln
Stefan Neumann
Virginia Vassilevska Williams

Cite As Get BibTex

Monika Henzinger, Andrea Lincoln, Stefan Neumann, and Virginia Vassilevska Williams. Conditional Hardness for Sensitivity Problems. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 26:1-26:31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ITCS.2017.26

Abstract

In recent years it has become popular to study dynamic problems in a sensitivity setting: Instead of allowing for an arbitrary sequence of updates, the sensitivity model only allows to apply batch updates of small size to the original input data. The sensitivity model is particularly appealing since recent strong conditional lower bounds ruled out fast algorithms for many dynamic problems, such as shortest paths, reachability, or subgraph connectivity.

In this paper we prove conditional lower bounds for these and additional problems in a sensitivity setting. For example, we show that under the Boolean Matrix Multiplication (BMM) conjecture combinatorial algorithms cannot compute the (4/3-\varepsilon)-approximate diameter of an undirected unweighted dense graph with truly subcubic preprocessing time and truly subquadratic update/query time. This result is surprising since in the static setting it is not clear whether a reduction from BMM to diameter is possible. We further show under the BMM conjecture that many problems, such as reachability or approximate shortest paths, cannot be solved faster than by recomputation from scratch even after only one or two edge insertions. We extend our reduction from BMM to Diameter to give a reduction from All Pairs Shortest Paths to Diameter under one deletion in weighted graphs. This is intriguing, as in the static setting it is a big open problem whether Diameter is as hard as APSP. We further get a nearly tight lower bound for shortest paths after two edge deletions based on the APSP conjecture. We give more lower bounds under the Strong Exponential Time Hypothesis. Many of our lower bounds also hold for static oracle data structures where no sensitivity is required.

Finally, we give the first algorithm for the (1+\varepsilon)-approximate radius, diameter, and eccentricity problems in directed or undirected unweighted graphs in case of single edges failures. The algorithm has a truly subcubic running time for graphs with a truly subquadratic number of edges; it is tight w.r.t. the conditional lower bounds we obtain.

Subject Classification

Keywords
  • sensitivity
  • conditional lower bounds
  • data structures
  • dynamic graph algorithms

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 FOCS, 2016. Google Scholar
  2. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic equivalences between graph centrality problems, APSP and diameter. In SODA, pages 1681-1697, 2015. Google Scholar
  3. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In FOCS, pages 434-443. IEEE, 2014. Google Scholar
  4. Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. Matching triangles and basing hardness on an extremely popular conjecture. In STOC, pages 41-50, 2015. Google Scholar
  5. V. L. Arlazarov, E. A. Dinic, M. A. Kronrod, and I. A. Faradzev. On economical construction of the transitive closure of an oriented graph. Soviet Math. Dokl., 11:1209-1210, 1970. Google Scholar
  6. Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant reachability for directed graphs. In DISC, pages 528-543, 2015. Google Scholar
  7. Surender Baswana, Keerti Choudhary, and Liam Roditty. Fault tolerant subgraph for single source reachability: Generic and optimal. In STOC, pages 509-518, 2016. Google Scholar
  8. Surender Baswana and Neelesh Khanna. Approximate shortest paths avoiding a failed vertex: Near optimal data structures for undirected unweighted graphs. Algorithmica, 66(1):18-50, 2013. Google Scholar
  9. Surender Baswana, Utkarsh Lath, and Anuradha S. Mehta. Single source distance oracle for planar digraphs avoiding a failed node or link. In SODA, pages 223-232, 2012. Google Scholar
  10. Aaron Bernstein and David Karger. A nearly optimal oracle for avoiding failed vertices and edges. In STOC, pages 101-110, 2009. Google Scholar
  11. Davide Bilò, Fabrizio Grandoni, Luciano Gualà, Stefano Leucci, and Guido Proietti. Improved purely additive fault-tolerant spanners. In ESA, 2015. Google Scholar
  12. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Fault-tolerant approximate shortest-path trees. In ESA, 2014. Google Scholar
  13. Davide Bilo, Luciano Guala, Stefano Leucci, and Guido Proietti. Compact and fast sensitivity oracles for single-source distances. In ESA, 2016. Google Scholar
  14. Davide Bilò, Luciano Gualà, Stefano Leucci, and Guido Proietti. Multiple-edge-fault-tolerant approximate shortest-path trees. In STACS, pages 18:1-18:14, 2016. Google Scholar
  15. Gilad Braunschvig, Shiri Chechik, and David Peleg. Fault tolerant additive spanners. In WG, 2012. Google Scholar
  16. Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In ITCS, pages 261-270, 2016. Google Scholar
  17. T. M. Chan. More algorithms for all-pairs shortest paths in weighted graphs. In STOC, pages 590-598, 2007. Google Scholar
  18. Shiri Chechik, Sarel Cohen, Amos Fiat, and Haim Kaplan. 1 + ε-approximate f-sensitive distance oracles. In SODA, 2017. Google Scholar
  19. Shiri Chechik, Michael Langberg, David Peleg, and Liam Roditty. f-sensitivity distance oracles and routing schemes. Algorithmica, 63(4):861-882, 2012. Google Scholar
  20. Keerti Choudhary. An optimal dual fault tolerant reachability oracle. In ICALP, pages 130:1-130:13, 2016. Google Scholar
  21. Søren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. In ICALP, pages 48:1-48:14, 2016. Google Scholar
  22. Ran Duan and Seth Pettie. Dual-failure distance and connectivity oracles. In SODA, pages 506-515, 2009. Google Scholar
  23. Ran Duan and Seth Pettie. Connectivity oracles for failure prone graphs. In STOC, pages 465-474, 2010. Google Scholar
  24. Ran Duan and Seth Pettie. Connectivity oracles for graphs subject to vertex failures. In SODA, 2017. Google Scholar
  25. François Le Gall. Powers of tensors and fast matrix multiplication. In ISSAC, pages 296-303, 2014. Google Scholar
  26. Fabrizio Grandoni and Virginia Vassilevska Williams. Improved distance sensitivity oracles via fast single-source replacement paths. In FOCS, pages 748-757, 2012. Google Scholar
  27. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In STOC, pages 21-30, 2015. Google Scholar
  28. Monika Henzinger and Stefan Neumann. Incremental and fully dynamic subgraph connectivity for emergency planning. In ESA, 2016. Google Scholar
  29. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  30. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  31. A. Itai and M. Rodeh. Finding a minimum circuit in a graph. SIAM J. Computing, 7(4):413-423, 1978. Google Scholar
  32. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher lower bounds from the 3sum conjecture. In SODA, pages 1272-1287, 2016. Google Scholar
  33. E. Nardelli, G. Proietti, and P. Widmayer. A faster computation of the most vital edge of a shortest path. Information Processing Letters, 79(2):81-85, 2001. Google Scholar
  34. Merav Parter. Dual failure resilient BFS structure. In PODC, pages 481-490, 2015. Google Scholar
  35. Merav Parter and David Peleg. Fault tolerant approximate bfs structures. In SODA, pages 1073-1092, 2014. Google Scholar
  36. Mihai Patrascu. Towards polynomial lower bounds for dynamic problems. In STOC, pages 603-610, 2010. Google Scholar
  37. Mihai Patrascu and Mikkel Thorup. Planning for fast connectivity updates. In FOCS, pages 263-271, 2007. Google Scholar
  38. L. Roditty and U. Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. In ICALP, pages 249-260, 2005. Google Scholar
  39. Liam Roditty and Uri Zwick. Replacement paths and k simple shortest paths in unweighted directed graphs. ACM Trans. Algorithms, 8(4):33, 2012. Google Scholar
  40. Virginia Vassilevska Williams. Faster replacement paths. In SODA, pages 1337-1346, 2011. Google Scholar
  41. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In STOC, pages 887-898, 2012. Google Scholar
  42. Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix and triangle problems. In FOCS, pages 645-654, 2010. 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