Near-Optimal Fully Dynamic Densest Subgraph

07/05/2019

∙

by   Saurabh Sawlani, et al.

∙

0

∙

share

We give the first fully dynamic algorithm which maintains a (1+ϵ)-approximate densest subgraph in worst-case time poly( n, ϵ^-1) per update with high probability. 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. Our result improves upon the previous best approximation factor of (4+ϵ) for fully dynamic densest subgraph obtained by [Bhattacharya-Henzinger-Nanongkai-Tsourakakis, STOC`15]. Our algorithm combines the uniform sparsification technique used in [Mitzenmacher-Pachocki-Peng-Tsourakakis-Xu, KDD`15] and [McGregor-Tench-Vorotnikova-Vu, MFCS`15] along with an augmenting path-like dual adjustment technique to maintain an approximate solution efficiently.