Proportionally Dense Subgraphs of Maximum Size.

The notion of density of a subgraph is usually defined as the number of edges in the subgraph divided by the number of its vertices. However, this definition is too permissive for the characterization of communities in graphs where each vertex should be densely connected within the community, with regard to its degree. Motivated by the idea of defining a notion of density more suitable for the study and identification of communities in graphs, we will be interested in the property of "proportional density". Specifically, we define a "proportionally dense subgraph" (PDS) as an induced subgraph such that each vertex in the PDS has proportionally more neighbors inside the PDS than in the whole graph. We will focus on the problem of finding a PDS of maximum size. Some hardness results on restricted classes of graphs will be presented (NP-hardness and APX-hardness), as well as a very simple polynomial-time 2-approximation algorithm. In the last part of the talk, we will give an upper bound on the size of a PDS in a graph based on its maximum degree and prove that all Hamiltonian cubic graphs have a PDS that reaches this bound.