Spectral Densest Subgraph and Independence Number of a Graph

Reid Andersen (Microsoft Research, USA)

Sebastian M. Cioabă (University of California, USA)

Abstract: In this paper, we study spectral versions of the densest subgraph problem and the largest independence subset problem. In the first part, we give an algorithm for identifying small subgraphs with large spectral radius. We also prove a Hoffman-type ratio bound for the order of an induced subgraph whose spectral radius is bounded from above.

Keywords: densest subgraph, eigenvalues, graphs, independence number

Categories: F.4.1