This paper presents a comprehensive study of algorithms for maintaining the number of all connected four-vertex subgraphs in a dynamic graph. Specifically, our algorithms maintain the number of any four-vertex subgraph, which is not a clique, in deterministic amortized update time $mathcal{O}(m^{1/2})$, resp., $mathcal{O}(m^{2/3})$. Queries can be answered in constant time. For length-3 paths, paws, 4-cycles, and diamonds these bounds match or are not far from (conditional) lower bounds: Based on the OMv conjecture we show that any dynamic algorithm that detects the existence of length-3 paths, 4-cycles, diamonds, or 4-cliques takes amortized update time $Omega(m^{1/2-delta})$. Additionally, for 4-cliques and all connected induced subgraphs, we show a lower bound of $Omega(m^{1-delta})$ for any small constant $delta > 0$ for the amortized update time, assuming the static combinatorial 4-clique conjecture holds. This shows that the $mathcal{O}(m)$ algorithm by Eppstein et al. [9] for these subgraphs cannot be improved by a polynomial factor.
تحميل البحث