Abstract
Reachability, distance, and matching are some of the most fundamental graph problems that have been of particular interest in dynamic complexity theory in recent years [Samir Datta et al., 2018; Samir Datta et al., 2018; Samir Datta et al., 2020]. Reachability can be maintained with firstorder update formulas, or equivalently in DynFO in general graphs with n nodes [Samir Datta et al., 2018], even under O(log(n)/log log(n)) changes per step [Samir Datta et al., 2018]. In the context of how large the number of changes can be handled, it has recently been shown [Samir Datta et al., 2020] that under a polylogarithmic number of changes, reachability is in DynFOpar in planar, bounded treewidth, and related graph classes  in fact in any graph where small nonzero circulation weights can be computed in NC.
We continue this line of investigation and extend the metatheorem for reachability to distance and bipartite maximum matching with the same bounds. These are amongst the most general classes of graphs known where we can maintain these problems deterministically without using a majority quantifier and even maintain witnesses. For the bipartite matching result, modifying the approach from [Stephen A. Fenner et al., 2016], we convert the static nonzero circulation weights to dynamic matchingisolating weights.
While reachability is in DynFOar under O(log(n)/log log(n)) changes, no such bound is known for either distance or matching in any nontrivial class of graphs under nonconstant changes. We show that, in the same classes of graphs as before, bipartite maximum matching is in DynFOar under O(log(n)/log log(n)) changes per step. En route to showing this we prove that the rank of a matrix can be maintained in DynFOar, also under O(log(n)/log log(n)) entry changes, improving upon the previous O(1) bound [Samir Datta et al., 2018]. This implies a similar extension for the nonuniform DynFO bound for maximum matching in general graphs and an alternate algorithm for maintaining reachability under O(log(n)/log log(n)) changes [Samir Datta et al., 2018].
BibTeX  Entry
@InProceedings{datta_et_al:LIPIcs.ICALP.2022.118,
author = {Datta, Samir and Gupta, Chetan and Jain, Rahul and Mukherjee, Anish and Sharma, Vimal Raj and Tewari, Raghunath},
title = {{Dynamic MetaTheorems for Distance and Matching}},
booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
pages = {118:1118:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772358},
ISSN = {18688969},
year = {2022},
volume = {229},
editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16459},
URN = {urn:nbn:de:0030drops164598},
doi = {10.4230/LIPIcs.ICALP.2022.118},
annote = {Keywords: Dynamic Complexity, Distance, Matching, Derandomization, Isolation, Matrix Rank}
}
Keywords: 

Dynamic Complexity, Distance, Matching, Derandomization, Isolation, Matrix Rank 
Collection: 

49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) 
Issue Date: 

2022 
Date of publication: 

28.06.2022 