Given a graph whose nodes may be coloured red, the parity of the number of red nodes can easily be maintained with first-order update rules in the dynamic complexity framework DynFO of Patnaik and Immerman. Can this be generalised to other or even all queries that are definable in first-order logic extended by parity quantifiers? We consider the query that asks whether the number of nodes that have an edge to a red node is odd. Already this simple query of quantifier structure parity-exists is a major roadblock for dynamically capturing extensions of first-order logic. We show that this query cannot be maintained with quantifier-free first-order update rules, and that variants induce a hierarchy for such update rules with respect to the arity of the maintained auxiliary relations. Towards maintaining the query with full first-order update rules, it is shown that degree-restricted variants can be maintained.

@article{paperbot1267,
  title = {Dynamic Complexity of Parity Exists Queries},
  author = {Nils Vortmeier and Thomas Zeume},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 4},
  year = {2021},
  doi = {10.46298/lmcs-17(4:9)2021}
}