Exploring the Subgraph Density-Size Trade-off via the Lovász Extension

Aritra Konar, Nicholas D. Sidiropoulos

Given an undirected graph, the Densest-k-Subgraph problem (DkS) seeks to find a subset of k vertices such that the sum of the edge weights in the corresponding subgraph is maximize…