[2505.12600] Fast and Simple Densest Subgraph with Predictions

Computer Science > Data Structures and Algorithms arXiv:2505.12600 (cs) [Submitted on 19 May 2025 (v1), last revised 14 Apr 2026 (this version, v3)] Title:Fast and Simple Densest Subgraph with Predictions Authors:Thai Bui, Luan Nguyen, Hoa T. Vu View a PDF of the paper titled Fast and Simple Densest Subgraph with Predictions, by Thai Bui and 2 other authors View PDF HTML (experimental) Abstract:We study the densest subgraph problem and its NP-hard densest at-most-$k$ subgraph variant through the lens of learning-augmented algorithms. We show that, given a reasonably accurate predictor that estimates whether a node belongs to the solution (e.g., a machine learning classifier), one can design simple linear-time algorithms that achieve a $(1-\epsilon)$approximation. Finally, we present experimental results demonstrating the effectiveness of our methods for the densest at-most-$k$ subgraph problem on real-world graphs. Subjects: Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG) Cite as: arXiv:2505.12600 [cs.DS]   (or arXiv:2505.12600v3 [cs.DS] for this version)   https://doi.org/10.48550/arXiv.2505.12600 Focus to learn more arXiv-issued DOI via DataCite Submission history From: Hoa Vu [view email] [v1] Mon, 19 May 2025 01:32:03 UTC (290 KB) [v2] Sun, 8 Feb 2026 22:43:12 UTC (617 KB) [v3] Tue, 14 Apr 2026 23:37:08 UTC (1,245 KB) Full-text links: Access Paper: View a PDF of the paper titled Fast and Simple Densest Subgraph with Predictions, by Thai Bui and 2 other...