Fast and Simple Densest Subgraph with Predictions
Not on the map. Why?
Abstract (arXiv)
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-ε)approximation. Finally, we present experimental results demonstrating the effectiveness of our methods for the densest at-most-k subgraph problem on real-world graphs.
Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 16 of its 43 references that are in the map. First posted on arXiv 19 May 2025.
Builds on
16 of 43 references.
References · 16
- 2020Algorithms with Predictionscited by 153
- 2022Faster Fundamental Graph Algorithms via Learned Predictionscited by 42
- 2022Maximum Flow and Minimum-Cost Flow in Almost-Linear Timecited by 28
- 2024Learning-augmented Maximum Independent Setcited by 11
- 2023A Survey on the Densest Subgraph Problem and Its Variantscited by 8
- 2024Learning-Augmented Streaming Algorithms for Approximating MAX-CUTcited by 8
- 2015k-center Clustering under Perturbation Resiliencecited by 6
- 2015Densest Subgraph in Dynamic Graph Streamscited by 6
- 2015Space- and Time-Efficient Algorithm for Maintaining Dense Subgraphs on One-Pass Dynamic Streamscited by 5
- 2019Near-Optimal Fully Dynamic Densest Subgraphcited by 5
- 2025Faster Global Minimum Cut with Predictionscited by 4
- 2019Flowless: Extracting Densest Subgraphs Without Flow Computationscited by 3
4 more
- 2015Applications of Uniform Sampling: Densest Subgraph and Beyondcited by 2
- 2019Distributed Dense Subgraph Detection and Low Outdegree Orientationcited by 2
- 2024Fast and Accurate Triangle Counting in Graph Streams Using Predictionscited by 2
- 2018Bilu-Linial stability, certified algorithms and the Independent Set problemcited by 1
Built on by
Not cited yet.