Dense and sparse graph partition

AbstractIn a graph G=(V,E), the density is the ratio between the number of edges |E| and the number of vertices |V|. This criterion may be used to find communities in a graph: groups of highly connected vertices. We propose an optimization problem based on this criterion; the idea is to find the vertex partition that maximizes the sum of the densities of each class. We prove that this problem is NP-hard by giving a reduction from graph-k-colorability. Additionally, we give a polynomial time algorithm for the special case of trees