Fast and Simple Densest Subgraph with Predictions
arXiv:2505.12600v3 Announce Type: replace-cross
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…