2025/05/19 by Thai Bui, Nguyen, Luan, Bui, Thai +1
Computer Science · #Advanced Graph Neural Networks #Complexity and Algorithms in Graphs #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2505.12600
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.