The Dynamic Complexity of Acyclic Hypergraph Homomorphisms
share
Finding a homomorphism from some hypergraph 𝒬 (or some relational structure) to another hypergraph 𝒟 is a fundamental problem in computer science. We show that an answer to this problem can be maintained under single-edge changes of 𝒬, as long as it stays acyclic, in the DynFO framework of Patnaik and Immerman that uses updates expressed in first-order logic. If additionally also changes of 𝒟 are allowed, we show that it is unlikely that existence of homomorphisms can be maintained in DynFO.
READ FULL TEXT