Dynamic Complexity of the Dyck Reachability

2016/10/24 by Bouyer, Patricia, Jugé, Vincent
#Computational Complexity (cs.CC) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1610.07499

Abstract

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.

Related

• A Note on Dynamic Bidirected Dyck-Reachability with Cycles
• Courcelle's Theorem Made Dynamic
• Reachability and Distances under Multiple Changes
• Dynamic complexity of Reachability: How many changes can we handle?
• The Decidability and Complexity of Interleaved Bidirected Dyck Reachability