DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2020.122

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

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

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

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.

Cite as

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)

Copy BibTex To Clipboard

@InProceedings{datta_et_al:LIPIcs.ICALP.2020.122,
  author =	{Datta, Samir and Kumar, Pankaj and Mukherjee, Anish and Tawari, Anuj and Vortmeier, Nils and Zeume, Thomas},
  title =	{{Dynamic Complexity of Reachability: How Many Changes Can We Handle?}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{122:1--122:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.122},
  URN =		{urn:nbn:de:0030-drops-125291},
  doi =		{10.4230/LIPIcs.ICALP.2020.122},
  annote =	{Keywords: Dynamic complexity, reachability, complex changes}
}

Search Results

Documents authored by Kumar, Pankaj

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

Abstract

Cite as

Thanks for your feedback!

Could not send message