# Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$

Let $$G=(V,E)$$ be a graph. Let $$m(G)=|E|$$ and $$n(G)=|V|$$. There are two different density definitions for $$G$$: $$d_1(G)=\frac{m(G)}{n(G)}$$ and $$d_2(G)=\frac{m(G)}{n(G)-1}.$$

Let $$H^* \subseteq G$$ be a subgraph of $$G$$ such that $$d_1 (H^*)\geq d_1 (H)$$ for any subgraph $$H\subseteq G$$.

My question is: Is it true that for any subgraph $$H\subseteq G$$ we still have $$d_2 (H^*)\geq d_2 (H)?$$

Any comment is welcome!

## Update 1:

J.G showed that the statement is NOT TRUE by providing a counterexample.

Consider two disjoint triangles connected by a single edge. Without checking too formally, $$𝐻^*$$ is the full graph with value $$7/6$$ under the first definition, but either of the triangles has value $$3/2$$ under the second definition while the full graph only has value $$7/5$$.

## Update 2:

I found that a maximum density subgraph (with the definition $$d_1(G)=\frac{m(G)}{n(G)}$$) can be found efficiently by using algorithms provided in references:

1. A. V. Goldberg. Finding a maximum density subgraph. Technical Report UCB/CSD-84-171, University of California at Berkeley, 1984.
2. G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. A Fast Parametric Maximum Flow Algorithm and Applications. SIAM Journal on Computing, 18(1):30–55, 1989.

However, I didn't find any reference for computing a maximum density subgraph (with the definition $$d_2 (G)=\frac{m(G)}{n(G)-1}$$). As pointed by J.G, a maximum $$d_1$$-density subgraph may not be a maximum $$d_2$$-density subgraph. My new question is:

Is there any efficient algorithm for computing a maximum density subgraph (with the definition $$d_2 (G)=\frac{m(G)}{n(G)-1}$$)?

• I think the second definition biases smaller sets, so no. Consider two disjoint triangles connected by a single edge. Without checking too formally, $H^*$ is the full graph with value $7/6$ under the first definition, but either of the triangles has value $3/2$ under the second definition while the full graph only has value $7/5$.
– J.G
Oct 10 '20 at 12:28
• @J.G Thanks. Your example really helps! Oct 10 '20 at 12:45
• It's not quite the same because of the rounding, but the maximum density of a subgraph under d2, rounded up to an integer, is just the arboricity, and can be computed in polynomial time by standard algorithms. See en.wikipedia.org/wiki/Arboricity and Nash-Williams (1964) "Decomposition of finite graphs into forests". Similarly the maximum density under d1, rounded up to an integer, is just pseudo-arboricity. Probably by applying these algorithms to a multigraph formed by replacing each edge by the same number of parallel edges you can counteract the rounding and get d2 itself. Oct 11 '20 at 7:27
• You may be interested in the following survey article about various types of graph density concepts and related results: A. Farago and Z. R.-Mojaveri, "In Search of the Densest Subgraph". Oct 11 '20 at 22:38

Here is a very slow algorithm, but it handles more general cases, like when density is defined as $$d_\beta(G) = \frac{m(G)}{n(G)-\beta}$$.

Let $$f$$ be a submodular function, $$g$$ be a modular function strictly larger than $$0$$. The min ratio problem $$\min_S f(S)/g(S)$$ can be solved in polynomial time. Indeed, use the standard to convert min ratio problem to parametric search problem with linear terms.

Consider we have input graph $$G=(V,E)$$. For $$d_\beta$$ density, fix a set $$T$$ of size $$k = \lfloor \beta \rfloor + 1$$, and define $$f_T:2^{V-T} \to \mathbb{R}$$ as $$f_T(S) = -m(G[T\cup S])$$, and define $$g_T:2^{V-T} \to \mathbb{R}_{>0}$$ as $$g_T(S) = |S|+|T|$$. You can check $$f$$ is submodular through a counting argument. Consider the optimum $$T$$ and $$S$$ for $$\min_{T:|T|=k, T\subset V} \min_{S:S\subset V\setminus T} f_T(S)/g_T(S).$$ Let $$T$$ and $$S$$ be the optimum of the problem. The densest subgraph is $$G[T\cup S]$$.

Running time is $$O(n^k)$$ calls to the min ratio oracle. Maybe faster algorithm exists, be nice to avoid that $$k$$ in the exponent.