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(logn, є−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 (1/4 − є) 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(logn/є) 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(logn, є−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.