Approximate Fully Dynamic Directed Densest Subgraph

Abstract

We give a fully dynamic algorithm maintaining a $(1-\epsilon )$-approximate directed densest subgraph in $\tilde{O}({\log }^3(n)/{\epsilon }^6)$ amortized time or $\tilde{O}({\log }^4(n)/{\epsilon }^7)$ worst-case time per edge update (where $\tilde{O}$ hides $\log \log$ factors), based on earlier work by Chekuri and Quanrud [arXiv:2210.02611, arXiv:2310.18146]. This result improves on earlier work done by Sawlani and Wang [arXiv:1907.03037], which guarantees $O({\log }^5(n)/{\epsilon }^7)$ worst case time for edge insertions and deletions.