Guaranteed Recovery of Planted Cliques and Dense Subgraphs by Convex Relaxation

Brendan P. W. Ames

We consider the problem of identifying the densest k-node subgraph in a given graph. We write this problem as an instance of rank-constrained cardinality minimization and then rela…