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 ( 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(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 fullydynamic 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. 1 We describe this connection explicitly in Sections 2 and 3.1.