Dynamic Subgraph Connectivity with Geometric Applications
Timothy M. Chan · SIAM Journal on Computing · 2006
Inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph $G=(V,E)$ and a subset of vertices $S \subseteq V$ to support insertions/deletions in S and connectivity queries (are two vertices connected?) in the subgraph induced by S. We develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using a combination of several simple ideas. Our method requires $\widetilde O(|E|^{4\omega/(3\omega+3)})=O(|E|^{0.94})$ amortized update time, and $\widetilde O(|E|^{1/3})$ query time, after $\widetilde O(|E|^{(5\omega+1)/(3\omega+3)})$ preprocessing time, where ω is the matrix multiplication exponent and $\widetilde O$ hides polylogarithmic factors.