Reachability and Distances under Multiple Changes

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 talk 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(+, \times) 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 any fixed natural number c. This talk is based on a paper with the same title, presented at ICALP 2018, which is joint work with Samir Datta, Anish Mukherjee and Thomas Zeume.

Authors

• Nils Vortmeier

Keywords

No keywords are indexed for this paper.