2026-07-23T08:16:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9124 2024-03-06T10:43:25Z ddc:004 open_access

Reachability and Distances under Multiple Changes Datta, Samir Mukherjee, Anish Vortmeier, Nils Zeume, Thomas dynamic complexity reachability distances complex changes 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Samir Datta and Anish Mukherjee and Nils Vortmeier and Thomas Zeume 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.120 urn:nbn:de:0030-drops-91245 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.120 eng https://creativecommons.org/licenses/by/3.0/legalcode