Fully dynamic connectivity on general graphs comes to mind. https://en.m.wikipedia.org/wiki/Dynamic_connectivity https://en.m.wikipedia.org/wiki/Dynamic_connect

Fully dynamic connectivity on general graphs comes to mind. https://en.m.wikipedia.org/wiki/Dynamic_connectivity https://en.m.wikipedia.org/wiki/Dynamic_connectivity (Graphs, with operations to connect and disconnect nodes, and to check whether two nodes are connected by some path.) State of the art there is poly-logarithmic time worst case.