Near-Optimal Fully Dynamic Densest Subgraph

We give the first fully dynamic algorithm which maintains a (1-ε)-approximate densest subgraph in worst-case time poly(log n, ε-1) per update. Dense subgraph discovery is an important primitive for many real-world applications such as community detection, link spam detection, distance query indexing, and computational biology. We approach the densest subgraph problem by framing its dual as a graph orientation problem, which we solve using an augmenting path-like adjustment technique. Our result improves upon the previous best approximation factor of left(frac14 - εright) for fully dynamic densest subgraph [Bhattacharya et. al., STOC `15]. We also extend our techniques to solving the problem on vertex-weighted graphs with similar runtimes. Additionally, we reduce the (1-ε)-approximate densest subgraph problem on directed graphs to O(log n/ε) instances of (1-ε)-approximate densest subgraph on vertex-weighted graphs. This reduction, together with our algorithm for vertex-weighted graphs, gives the first fully-dynamic algorithm for directed densest subgraph in worst-case time poly(log n, ε-1) per update. Moreover, combined with a near-linear time algorithm for densest subgraph [Bahmani et. al., WAW `14], this gives the first near-linear time algorithm for directed densest subgraph.