Document Open Access Logo

Dynamic Complexity of Reachability: How Many Changes Can We Handle?

Authors Samir Datta, Pankaj Kumar, Anish Mukherjee , Anuj Tawari, Nils Vortmeier, Thomas Zeume

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.122.pdf
  • Filesize: 0.56 MB
  • 19 pages

Document Identifiers

Author Details

Samir Datta
  • Chennai Mathematical Institute, India
Pankaj Kumar
  • Chennai Mathematical Institute, India
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic
Anish Mukherjee
  • Institute of Informatics, University of Warsaw, Poland
Anuj Tawari
  • Chennai Mathematical Institute, India
Nils Vortmeier
  • TU Dortmund, Germany
Thomas Zeume
  • Ruhr-Universität Bochum, Germany

Funding

  • Datta, Samir: The author was partially funded by a grant from Infosys foundation and SERB-MATRICS grant MTR 000480.
  • Kumar, Pankaj: The author was supported by Czech Science Foundation GAČR (grant #19-27871X).
  • Mukherjee, Anish: The author was supported by the ERC CoG grant TUgbOAT no 772346.
  • Vortmeier, Nils: The author acknowledges the financial support by DFG grant SCHW 678/6-2.

Acknowledgements

The first author would like to thank Chetan Gupta for finding a problem in a previous version of the proof of Theorem 14.

Cite As Get BibTex

Samir Datta, Pankaj Kumar, Anish Mukherjee, Anuj Tawari, Nils Vortmeier, and Thomas Zeume. Dynamic Complexity of Reachability: How Many Changes Can We Handle?. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 122:1-122:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.122

Abstract

In 2015, it was shown that reachability for arbitrary directed graphs can be updated by first-order formulas after inserting or deleting single edges. Later, in 2018, this was extended for changes of size (log n)/(log log n), where n is the size of the graph. Changes of polylogarithmic size can be handled when also majority quantifiers may be used.
In this paper we extend these results by showing that, for changes of polylogarithmic size, first-order update formulas suffice for maintaining (1) undirected reachability, and (2) directed reachability under insertions. For classes of directed graphs for which efficient parallel algorithms can compute non-zero circulation weights, reachability can be maintained with update formulas that may use "modulo 2" quantifiers under changes of polylogarithmic size. Examples for these classes include the class of planar graphs and graphs with bounded treewidth. The latter is shown here.
As the logics we consider cannot maintain reachability under changes of larger sizes, our results are optimal with respect to the size of the changes.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
Keywords
  • Dynamic complexity
  • reachability
  • complex changes

Metrics

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

Related Versions

References

  1. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC¹. J. Comput. Syst. Sci., 41(3):274-306, 1990. URL: https://doi.org/10.1016/0022-0000(90)90022-D.
  2. Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio, and Li-Yang Tan. Near-optimal small-depth lower bounds for small distance connectivity. In Daniel Wichs and Yishay Mansour, editors, Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 612-625. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897534.
  3. Samir Datta, William Hesse, and Raghav Kulkarni. Dynamic complexity of directed reachability and other problems. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 356-367. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_30.
  4. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. J. ACM, 65(5):33:1-33:24, August 2018. URL: https://doi.org/10.1145/3212685.
  5. Samir Datta, Raghav Kulkarni, Raghunath Tewari, and N. V. Vinodchandran. Space complexity of perfect matching in bounded genus bipartite graphs. J. Comput. Syst. Sci., 78(3):765-779, 2012. URL: https://doi.org/10.1016/j.jcss.2011.11.002.
  6. Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A Strategy for Dynamic Programs: Start over and Muddle through. Logical Methods in Computer Science, Volume 15, Issue 2, May 2019. URL: https://doi.org/10.23638/LMCS-15(2:12)2019.
  7. Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume. Reachability and distances under multiple changes. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 120:1-120:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.120.
  8. Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume. Reachability and distances under multiple changes. CoRR, abs/1804.08555, 2018. URL: http://arxiv.org/abs/1804.08555.
  9. Guozhu Dong and Jianwen Su. Arity bounds in first-order incremental evaluation and definition of polynomial time database queries. J. Comput. Syst. Sci., 57(3):289-308, 1998. URL: https://doi.org/10.1006/jcss.1998.1565.
  10. Michael Elberfeld, Andreas Jakoby, and Till Tantau. Logspace versions of the theorems of Bodlaender and Courcelle. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA, pages 143-152. IEEE Computer Society, 2010. URL: https://doi.org/10.1109/FOCS.2010.21.
  11. Alexander Healy and Emanuele Viola. Constant-depth circuits for arithmetic in finite fields of characteristic two. In Bruno Durand and Wolfgang Thomas, editors, STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings, volume 3884 of Lecture Notes in Computer Science, pages 672-683. Springer, 2006. URL: https://doi.org/10.1007/11672142_55.
  12. Harold V Henderson and Shayle R Searle. On deriving the inverse of a sum of matrices. Siam Review, 23(1):53-60, 1981. Google Scholar
  13. William Hesse. The dynamic complexity of transitive closure is in DynTC^0. Theor. Comput. Sci., 296(3):473-485, 2003. URL: https://doi.org/10.1016/S0304-3975(02)00740-5.
  14. William Hesse, Eric Allender, and David A. Mix Barrington. Uniform constant-depth threshold circuits for division and iterated multiplication. J. Comput. Syst. Sci., 65(4):695-716, 2002. URL: https://doi.org/10.1016/S0022-0000(02)00025-9.
  15. Neil Immerman. Nondeterministic space is closed under complementation. SIAM J. Comput., 17(5):935-938, 1988. URL: https://doi.org/10.1137/0217058.
  16. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: https://doi.org/10.1007/978-1-4612-0539-5.
  17. Stasys Jukna. Boolean function complexity: advances and frontiers, volume 27. Springer Science & Business Media, 2012. Google Scholar
  18. Vivek Anand T. Kallampally and Raghunath Tewari. Trading determinism for time in space bounded computations. In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, pages 10:1-10:13, 2016. URL: https://doi.org/10.4230/LIPIcs.MFCS.2016.10.
  19. Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199-209, 1997. URL: https://doi.org/10.1006/jcss.1997.1520.
  20. Thomas Schwentick and Thomas Zeume. Dynamic complexity: recent updates. SIGLOG News, 3(2):30-52, 2016. URL: https://doi.org/10.1145/2948896.2948899.
  21. Roman Smolensky. Algebraic methods in the theory of lower bounds for boolean circuit complexity. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 77-82, 1987. URL: https://doi.org/10.1145/28395.28404.
  22. Róbert Szelepcsényi. The method of forced enumeration for nondeterministic automata. Acta Inf., 26(3):279-284, 1988. URL: https://doi.org/10.1007/BF00299636.
  23. Raghunath Tewari and N. V. Vinodchandran. Green’s theorem and isolation in planar graphs. Inf. Comput., 215:1-7, 2012. URL: https://doi.org/10.1016/j.ic.2012.03.002.
  24. Nils Vortmeier. Dynamic expressibility under complex changes. PhD thesis, TU Dortmund University, Germany, 2019. URL: https://doi.org/10.17877/DE290R-20434.
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