Variants of Densest Subgraph Problems

Question

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?)

Answer 1

This is meant more as a comment than as a solution, but is a bit too long to fit in the comment box. There is a bit of handwaving and ignoring of small factors, but I can formalize the work below further if requested.

Here's a heuristic reason why (a) might be difficult to approximate within a small factor.

Consider the random-in-random PLANTED DENSE SUBGRAPH problem, which one to reliably distinguish between the Erdos-Renyi graph $G(n,p)$ and the graph $G(n,p)$ with a planted $G(n',p')$ for certain values of $n,n',p,p'$. It is a difficult problem -- conjectured hard by some -- to do this in polynomial time for $p = \frac{1}{n^{1/2}}$, $n' = n^{1/2}$, $p' = \frac{1}{n^{1/4 + \epsilon}}$. That is, it's hard to distinguish a "pure" $G(n,1/\sqrt{n})$ graph (where each induced subgraph of size $\sqrt{n}$ has average degree near $1$) from instances where some subset of $\sqrt{n}$ vertices has so many edges planted between them that the average degree is roughly $n^{1/4 - \epsilon}$.

In such instances, there's quite a large gap in the maximum edge densities in subgraphs of size at least $\sqrt{n}$. In particular, while the planted portion of the planted-instance graph has edge density roughly $\frac{1}{n^{1/4+\epsilon}}$, just about any size $\sqrt{n}$ (or higher) subgraph of the non-planted $G(n,1/\sqrt{n})$ graph will have edge density about $1/\sqrt{n}$, a gap of roughly $n^{1/4 - \epsilon}$.

Any approximation algorithm with a stronger guarantee than $n^{1/4 - \epsilon}$ can thus be used to solve a conjectured-hard class of instances of Planted-DkS.

Answer 2

The edge density as you define it is often used in extremal graph theory. See for example the textbook of Diestel, where he defines it under this name in the chapter on extremal graph theory. It is a useful notion especially when considering dense graph classes, then the lim sup of edge densities from the class will go to something interesting below 1. See for example the famous theorem of Erdös and Simonovits.

The lim sup for a sparse graph class will always go to $0$ and we gain no insight from this. When considering sparse graph classes and also when analysing algorithms, the notion of average degree is more useful.

I do not know of any algorithmic results using the definition of edge density. Maybe it might be interesting to you that if you drop $k$ completely, i.e., if you just want to find the densest subgraph, this can be done in polynomial time.