Reachability Is in DynFO
Samir K. Datta, Raghav Kulkarni, Anish Mukherjee, Thomas Schwentick, Thomas Zeume · Journal of the ACM · 2018
Patnaik and Immerman introduced the dynamic complexity class DynFO of database queries that can be maintained by first-order dynamic programs with the help of auxiliary relations under insertions and deletions of edges. This article confirms their conjecture that the reachability query is in DynFO. As a byproduct, it is shown that the rank of a matrix with small values can be maintained in DynFO. It is further shown that the (size of the) maximum matching of a graph can be maintained in non-uniform DynFO, an extension of DynFO, with non-uniform initialisation of the auxiliary relations.