Lazy or eager dynamic matching may not be fast

Abstract We consider two sub-classes of fully dynamic algorithms for maintaining a maximal matching, which we define as lazy algorithms and eager algorithms. We prove a conditional lower bound which is sub-linear in the number of edges for the update time of lazy algorithms and eager algorithms. Our result is conditioned on the well known conjecture about the hardness of triangle detection in a graph.