On the quantifier-free dynamic complexity of Reachability

Thomas Zeume

The dynamic complexity of the reachability query is studied in the dynamic complexity framework of Patnaik and Immerman, restricted to quantifier-free update formulas.

It is shown that, with this restriction, the reachability query cannot be dynamically maintained, neither with binary auxiliary relations nor with unary auxiliary functions, and that ternary auxiliary relations are more powerful with respect to graph queries than binary auxiliary relations. It is also established that Reachability cannot be maintained with auxiliary relations or functions of arbitrary arity in the scenario, where update sequences are applied to a non-empty graph and the initialization of the auxiliary relations is permutation-invariant. Furthermore, the inexpressibility results are transferred to some other queries and some normal forms are established.