  Dynamic complexity is concerned with updating the output of a problem when
the input is slightly changed. We study the dynamic complexity of Dyck
reachability problems in directed and undirected graphs, where updates may add
or delete edges. We show a strong dichotomy between such problems, based on the
size of the Dyck alphabet. Some of them are P-complete (under a strong notion
of reduction) while the others lie either in DynFO or in NL.
