A Scalable and Exact Relaxation for Densest $k$-Subgraph via Error Bounds

Ya Liu, Junbin Liu, Wing-Kin Ma +1

Given an undirected graph and a size parameter $k$, the Densest $k$-Subgraph (D$k$S) problem extracts the subgraph on $k$ vertices with the largest number of induced edges. While D…