License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2018.120
URN: urn:nbn:de:0030-drops-91245
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9124/
Go to the corresponding LIPIcs Volume Portal

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

Reachability and Distances under Multiple Changes

pdf-format:
LIPIcs-ICALP-2018-120.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{datta_et_al:LIPIcs:2018:9124,
  author =	{Samir Datta and Anish Mukherjee and Nils Vortmeier and Thomas Zeume},
  title =	{{Reachability and Distances under Multiple Changes}},
  booktitle =	{45th International Colloquium on Automata, Languages, and  Programming (ICALP 2018)},
  pages =	{120:1--120:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9124},
  URN =		{urn:nbn:de:0030-drops-91245},
  doi =		{10.4230/LIPIcs.ICALP.2018.120},
  annote =	{Keywords: dynamic complexity, reachability, distances, complex changes}
}

Keywords: dynamic complexity, reachability, distances, complex changes
Collection: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Issue Date: 2018
Date of publication: 04.07.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI