2021/07/13 by Nils Vortmeier, Vortmeier, Nils, Ioannis Kokkinis +1
Computer Science · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Logic in Computer Science (cs.LO) #cs.CC #cs.LO
paper · pdf · doi:10.48550/arxiv.2107.06121
arxiv created 2021/07/13 · arxiv updated 2021/07/14
Finding a homomorphism from some hypergraph Q (or some relational structure) to another hypergraph D is a fundamental problem in computer science. We show that an answer to this problem can be maintained under single-edge changes of Q, 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 D are allowed, we show that it is unlikely that existence of homomorphisms can be maintained in DynFO.