A deterministic approximation algorithm for the densest \(k\)-subgraph problem (Q2427738)

Summary: In the Densest \(k\)-Subgraph Problem (DSP), we are given an undirected weighted graph \(G = (V, E)\) with \(n\) vertices \((v_1,\dots , v_n)\). We seek to find a subset of \(k\) vertices (\(k\) belonging to \({1,\dots , n}\)) which maximises the number of edges which have their two endpoints in the subset. This problem is NP-hard even for bipartite graphs, and no polynomial-time algorithm with a constant performance guarantee is known for the general case. Several authors have proposed randomised approximation algorithms for particular cases (especially when \(k = n/c, c>1\)). But derandomisation techniques are not easy to apply here because of the cardinality constraint, and can have a high computational cost. In this paper, we present a deterministic \(\max(d, 8/9c)\)-approximation algorithm for the DSP (where d is the density of G). The complexity of our algorithm is only that of linear programming. This result is obtained by using particular optimal solutions of a linear programme associated with the classical 0-1 quadratic formulation of DSP.