Given a graph $G$, and a vertex-induced subgraph $H$ of $G$, there are two superficially-similar definitions ways to define the density of $H$:
(1) Average degree of vertices in $H$
(2) What I will refer to as the "edge density" of $H$, defined as $\frac{ E(H) }{ \binom{V(H)}{2}}$.
I'm interested in understanding the complexity of finding dense subgraphs, subject to constraints on the number of nodes, using the second definition of density. Unfortunately, most of the relevant work I can find, most notably on variants of the $k$-densest subgraph problem, uses the first definition. I'm looking for pointers to work on the second definition. First, I will elaborate on the similarities and differences between the two definitions before asking two specific questions.
If one is interested in finding the densest subgraph with a given number of nodes $k$, it doesn't matter which definition you use. The two definitions coincide when comparing subgraphs with the same number of nodes. The result is the NP-hard $k$-densest subgraph problem, which is well studied, but who's complexity of approximation remains poorly understood. However,when looking for the "densest at-most-k subgraph" or "densest at-least-k" subgraph, the two definitions of density appear importantly different.
Densest at-most-k subgraph: Using the average-degree definition, this problem is NP-hard, and its approximability is essentially equivalent to that of the classic "k-densest subgraph" problem [Anderson and Chellapilla '09]. Using the edge density definition, however, this problem is trivial: any two nodes connected by an edge are an optimal choice of $H$.
Densest at-least-k subgraph: Using the average-degree definition, this problem has been studied before, and admits a constant factor approximation [Anderson and Chellapilla '09]. However, using the edge density definition, I can't seem to find any related work.
This get more dicey when one considers both upper and lower bounds on $k$, the number of nodes in the sought induced subgraph.
My questions:
(a) Can anyone point me to work on approximation algorithms for densest at-least-k subgraph using the edge-density definition of density?
(b) What is the proper name of what I'm calling "edge density"? Why does this definition appear more esoteric, as far as the approximation algorithms community is concerned, than the average degree definition? (Or is it?)