Learning-Augmented Approximation Algorithms for Densest $k$-Subgraph

We study learning-augmented approximation algorithms for the Densest $k$-Subgraph (DkS) problem under vertex and edge predictions. In the persistent Vertex Prediction Model, each vertex receives a single noisy prediction of its membership in a fixed, unknown optimum $S^{\star }$; the predictions are independent and each is correct with probability $1/2+ϵ$. We give a polynomial-time algorithm that requires no knowledge of $ϵ$ and combines a prediction-guided construction with prediction-free approximation algorithms. For every even $k\ge 2$, it achieves, with high probability over the predictions, an $O_{\eta }\left(\min \left\{k,1+\sqrt{\Delta \log n}/ϵ,n^{1/4+\eta }\right\}\right)$-approximation, where $\Delta$ is the maximum degree and $\eta >0$ is fixed. Under the Strongish Planted Clique Hypothesis (SPCH), we show that there is a constant $c>0$ such that, for every fixed $0<ϵ<1/2$, no randomized polynomial-time algorithm using persistent vertex predictions achieves an $o(k)$-approximation or, separately, an $O(2^{c(\log n{)}^{2/3}})$-approximation with constant success probability. We also establish approximation guarantees for non-persistent vertex predictions and edge predictions. Experiments on real-world and planted graphs with up to millions of vertices show that moderately informative predictions often improve solution quality over prediction-free baselines while maintaining practical running times.