| Summary: | 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.
|
|---|