Let $G=(V,E)$ be an undirected graph. Suppose that we partition the nodes into groups $C_1,C_2,\ldots,C_k$. The score of group $C_i$ is $E(C_i)/n(C_i)$, where $E(C_i)$ is the number of edges within $C_i$, and $n(C_i)$ is the number of vertices within $C_i$. The score of the partition is the sum of the score of its groups.
Is there a fast (polynomial time) algorithm to find a partition with the maximal score? (if there is more than one such partition, the algorithm can find any of them.)
It was shown a couple of years ago that the problem was NP-Hard, from a reduction to k-colorability.
See the paper here : http://hal.inria.fr/docs/00/45/49/99/PDF/dense_graph_partition.pdf