$(1-\epsilon )$-approximate fully dynamic densest subgraph: linear space and faster update time

Abstract

We consider the problem of maintaining a $(1-\epsilon )$-approximation to the densest subgraph (DSG) in an undirected multigraph as it undergoes edge insertions and deletions (the fully dynamic setting). Sawlani and Wang [SW20] developed a data structure that, for any given $\epsilon >0$, maintains a $(1-\epsilon )$-approximation with $O({\log }^{4}n/{\epsilon }^6)$ worst-case update time for edge operations, and $O(1)$ query time for reporting the density value. Their data structure was the first to achieve near-optimal approximation, and improved previous work that maintained a $(1/4-\epsilon )$ approximation in amortized polylogarithmic update time [BHNT15]. In this paper we develop a data structure for $(1-\epsilon )$-approximate DSG that improves the one from [SW20] in two aspects. First, the data structure uses linear space improving the space bound in [SW20] by a logarithmic factor. Second, the data structure maintains a $(1-\epsilon )$-approximation in amortized $O({\log }^{2}n/{\epsilon }^4)$ time per update while simultaneously guaranteeing that the worst case update time is $O({\log }^{3}n\log \log n/{\epsilon }^6)$. We believe that the space and update time improvements are valuable for current large scale graph data sets. The data structure extends in a natural fashion to hypergraphs and yields improvements in space and update times over recent work [BBCG22] that builds upon [SW20].