Document Open Access Logo

Reachability and Distances under Multiple Changes

Authors Samir Datta, Anish Mukherjee, Nils Vortmeier, Thomas Zeume

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.120.pdf
  • Filesize: 469 kB
  • 14 pages

Document Identifiers

Author Details

Samir Datta
  • Chennai Mathematical Institute & UMI ReLaX, Chennai, India
Anish Mukherjee
  • Chennai Mathematical Institute, Chennai, India
Nils Vortmeier
  • TU Dortmund University, Dortmund, Germany
Thomas Zeume
  • TU Dortmund University, Dortmund, Germany

Funding

The authors acknowledge the financial support by the DAAD-DST grant "Exploration of New Frontiers in Dynamic Complexity". The first and the second authors were partially funded by a grant from Infosys foundation. The second author was partially supported by a TCS PhD fellowship. The last two authors acknowledge the financial support by DFG grant SCHW 678/6-2 on "Dynamic Expressiveness of Logics".

Cite AsGet BibTex

Samir Datta, Anish Mukherjee, Nils Vortmeier, and Thomas Zeume. Reachability and Distances under Multiple Changes. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 120:1-120:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.120

Abstract

Recently it was shown that the transitive closure of a directed graph can be updated using first-order formulas after insertions and deletions of single edges in the dynamic descriptive complexity framework by Dong, Su, and Topor, and Patnaik and Immerman. In other words, Reachability is in DynFO. In this article we extend the framework to changes of multiple edges at a time, and study the Reachability and Distance queries under these changes. We show that the former problem can be maintained in DynFO(+, x) under changes affecting O({log n}/{log log n}) nodes, for graphs with n nodes. If the update formulas may use a majority quantifier then both Reachability and Distance can be maintained under changes that affect O(log^c n) nodes, for fixed c in N. Some preliminary results towards showing that distances are in DynFO are discussed.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Theory of computation → Finite Model Theory
Keywords
  • dynamic complexity
  • reachability
  • distances
  • complex changes

Metrics

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

Related Versions

References

  1. Manindra Agrawal and V Vinay. Arithmetic circuits: A chasm at depth four. In Foundations of Computer Science, 2008. FOCS'08. IEEE 49th Annual IEEE Symposium on, pages 67-75. IEEE, 2008. Google Scholar
  2. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC¹. J. Comput. Syst. Sci., 41(3):274-306, 1990. URL: http://dx.doi.org/10.1016/0022-0000(90)90022-D.
  3. Stephen A. Cook. A taxonomy of problems with fast parallel algorithms. Information and Control, 64(1-3):2-21, 1985. URL: http://dx.doi.org/10.1016/S0019-9958(85)80041-3.
  4. Samir Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, and Thomas Zeume. Reachability is in DynFO. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 159-170. Springer, 2015. URL: http://dx.doi.org/10.1007/978-3-662-47666-6.
  5. Samir Datta, Anish Mukherjee, Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. A strategy for dynamic programs: Start over and muddle through. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, volume 80 of LIPIcs, pages 98:1-98:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://www.dagstuhl.de/dagpub/978-3-95977-041-5, URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.98.
  6. 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.
  7. Guozhu Dong and Chaoyi Pang. Maintaining transitive closure in first order after node-set and edge-set deletions. Inf. Process. Lett., 62(4):193-199, 1997. URL: http://dx.doi.org/10.1016/S0020-0190(97)00066-5.
  8. Guozhu Dong, Jianwen Su, and Rodney W. Topor. Nonrecursive incremental evaluation of datalog queries. Ann. Math. Artif. Intell., 14(2-4):187-223, 1995. URL: http://dx.doi.org/10.1007/BF01530820.
  9. Kousha Etessami. Dynamic tree isomorphism via first-order updates. In Proceedings of the Seventeenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 235-243, 1998. URL: http://dx.doi.org/10.1145/275487.275514.
  10. Chris D. Godsil. Algebraic combinatorics. Chapman and Hall mathematics series. Chapman and Hall, 1993. Google Scholar
  11. Erich Grädel and Sebastian Siebertz. Dynamic definability. In Alin Deutsch, editor, 15th International Conference on Database Theory, ICDT '12, Berlin, Germany, March 26-29, 2012, pages 236-248. ACM, 2012. URL: http://dl.acm.org/citation.cfm?id=2274576, URL: http://dx.doi.org/10.1145/2274576.2274601.
  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: http://dx.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: http://dx.doi.org/10.1016/S0022-0000(02)00025-9.
  15. Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012. Google Scholar
  16. Neil Immerman. Descriptive complexity. Graduate texts in computer science. Springer, 1999. URL: http://dx.doi.org/10.1007/978-1-4612-0539-5.
  17. Meena Mahajan and V. Vinay. Determinant: Old algorithms, new insights. SIAM J. Discrete Math., 12(4):474-490, 1999. URL: http://dx.doi.org/10.1137/S0895480198338827.
  18. Sushant Patnaik and Neil Immerman. Dyn-fo: A parallel, dynamic complexity class. In Victor Vianu, editor, Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 24-26, 1994, Minneapolis, Minnesota, USA, pages 210-221. ACM Press, 1994. URL: http://dl.acm.org/citation.cfm?id=182591, URL: http://dx.doi.org/10.1145/182591.182614.
  19. Sushant Patnaik and Neil Immerman. Dyn-FO: A parallel, dynamic complexity class. J. Comput. Syst. Sci., 55(2):199-209, 1997. URL: http://dx.doi.org/10.1006/jcss.1997.1520.
  20. Thomas Schwentick, Nils Vortmeier, and Thomas Zeume. Dynamic complexity under definable changes. In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, volume 68 of LIPIcs, pages 19:1-19:18. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. URL: http://www.dagstuhl.de/dagpub/978-3-95977-024-8, URL: http://dx.doi.org/10.4230/LIPIcs.ICDT.2017.19.
  21. Thomas Schwentick and Thomas Zeume. Dynamic complexity: recent updates. SIGLOG News, 3(2):30-52, 2016. URL: http://dx.doi.org/10.1145/2948896.2948899.
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 Imprint Privacy Contact