<p>Here is a very slow algorithm, but it handles more general cases, like when density is defined as <span class="math-container">$d_\beta(G) = \frac{m(G)}{n(G)-\beta}$</span>.</p>
<p>Let <span class="math-container">$f$</span> be a submodular function, <span class="math-container">$g$</span> be a modular function strictly larger than <span class="math-container">$0$</span>. The min ratio problem <span class="math-container">$\min_S f(S)/g(S)$</span> can be solved in polynomial time. Indeed, use the standard to convert min ratio problem to parametric search problem with linear terms.</p>
<p>Consider we have input graph <span class="math-container">$G=(V,E)$</span>.
For <span class="math-container">$d_\beta$</span> density, fix a set <span class="math-container">$T$</span> of size <span class="math-container">$k = \lfloor \beta \rfloor + 1$</span>, and define <span class="math-container">$f_T:2^{V-T} \to \mathbb{R}$</span> as <span class="math-container">$f_T(S) = -m(G[T\cup S])$</span>, and define <span class="math-container">$g_T:2^{V-T} \to \mathbb{R}_{&gt;0}$</span> as <span class="math-container">$g_T(S) = |S|+|T|$</span>. You can check <span class="math-container">$f$</span> is submodular through a counting argument.
Consider the optimum <span class="math-container">$T$</span> and <span class="math-container">$S$</span> for <span class="math-container">$$\min_{T:|T|=k, T\subset V} \min_{S:S\subset V\setminus T} f_T(S)/g_T(S).$$</span> Let <span class="math-container">$T$</span> and <span class="math-container">$S$</span> be the optimum of the problem. The densest subgraph is <span class="math-container">$G[T\cup S]$</span>.</p>
<p>Running time is <span class="math-container">$O(n^k)$</span> calls to the min ratio oracle. Maybe faster algorithm exists, be nice to avoid that <span class="math-container">$k$</span> in the exponent.</p>

CC BY-SA 4.0
2020-10-12T11:47:24.107Z
2020-10-15T00:08:28.123Z
2020-10-15T00:08:28.123Z
Chao Xu
<p>Let <span class="math-container">$G=(V,E)$</span> be a graph.
Let <span class="math-container">$m(G)=|E|$</span> and <span class="math-container">$n(G)=|V|$</span>.
There are two different density definitions for <span class="math-container">$G$</span>:
<span class="math-container">$$d_1(G)=\frac{m(G)}{n(G)}$$</span>
and
<span class="math-container">$$d_2(G)=\frac{m(G)}{n(G)-1}.$$</span></p>
<p>Let <span class="math-container">$H^* \subseteq G$</span> be a subgraph of <span class="math-container">$G$</span> such that
<span class="math-container">$$d_1 (H^*)\geq d_1 (H)$$</span>
for any subgraph <span class="math-container">$H\subseteq G$</span>.</p>
<p>My question is:
<strong>Is it true that for any subgraph <span class="math-container">$H\subseteq G$</span> we still have</strong>
<span class="math-container">$$d_2 (H^*)\geq d_2 (H)?$$</span></p>
<p>Any comment is welcome!</p>
<h2><strong>Update 1:</strong></h2>
<p><a href="https://cstheory.stackexchange.com/questions/47697/two-different-graph-densities-e-v-and-e-v-1?noredirect=1#comment106120_47697">J.G</a> showed that the statement is <strong>NOT TRUE</strong> by providing a counterexample.</p>
<blockquote>
<p><em>Consider two disjoint triangles connected by a single edge. Without checking too formally, <span class="math-container">$^*$</span> is the full graph with value <span class="math-container">$7/6$</span> under the first definition, but either of the triangles has value <span class="math-container">$3/2$</span> under the second definition while the full graph only has value <span class="math-container">$7/5$</span>.</em></p>
</blockquote>
<h2><strong>Update 2:</strong></h2>
<p>I found that a maximum density subgraph (with the definition <span class="math-container">$d_1(G)=\frac{m(G)}{n(G)}$</span>) can be found efficiently by using algorithms provided in references:</p>
<ol>
<li>A. V. Goldberg. <em><a href="https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5956.html" rel="nofollow noreferrer">Finding a maximum density subgraph</a></em>. Technical Report UCB/CSD-84-171, University of California at Berkeley, 1984.</li>
<li>G. Gallo, M. D. Grigoriadis, and R. E. Tarjan. <em><a href="https://epubs.siam.org/doi/abs/10.1137/0218003" rel="nofollow noreferrer">A Fast Parametric Maximum Flow Algorithm and Applications</a>.</em> SIAM Journal on Computing, 18(1):30–55, 1989.</li>
</ol>
<p>However, I didn't find any reference for computing a maximum density subgraph (with the definition <span class="math-container">$d_2 (G)=\frac{m(G)}{n(G)-1}$</span>).
As pointed by <a href="https://cstheory.stackexchange.com/questions/47697/two-different-graph-densities-e-v-and-e-v-1?noredirect=1#comment106120_47697">J.G</a>, a maximum <span class="math-container">$d_1$</span>-density subgraph may not be a maximum <span class="math-container">$d_2$</span>-density subgraph.
My new question is:</p>
<p><strong>Is there any efficient algorithm for computing a maximum density subgraph (with the definition <span class="math-container">$d_2 (G)=\frac{m(G)}{n(G)-1}$</span>)?</strong></p>

CC BY-SA 4.0
2020-10-10T12:28:00.180Z
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$.
Jason Gaitonde
CC BY-SA 4.0
2020-10-10T12:45:08.607Z
@J.G Thanks. Your example really helps!
hxiao
CC BY-SA 4.0
2020-10-11T07:27:07.290Z
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 https://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.
David Eppstein
CC BY-SA 4.0
2020-10-11T22:38:29.023Z
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"](https://www.mdpi.com/1999-4893/12/8/157).
Andras Farago
<graph-theory>
Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$
hxiao
# Two different graph densities: $|E|/|V|$ and $|E|/(|V|-1)$

(Asked by: username_0 on 2020-10-10)

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](https://cstheory.stackexchange.com/questions/47697/two-different-graph-densities-e-v-and-e-v-1?noredirect=1#comment106120_47697) 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](https://www2.eecs.berkeley.edu/Pubs/TechRpts/1984/5956.html)*. 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](https://epubs.siam.org/doi/abs/10.1137/0218003).* 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](https://cstheory.stackexchange.com/questions/47697/two-different-graph-densities-e-v-and-e-v-1?noredirect=1#comment106120_47697), 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}$)?**

**Tags:** graph-theory
> **Comments:**
> **username_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$.  
> **username_0**: @J.G Thanks. Your example really helps!  
> **username_2**: 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 https://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.  
> **username_3**: 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"](https://www.mdpi.com/1999-4893/12/8/157).  

---

## 1 answers

### Answer by username_4 on 2020-10-12. Score: 2

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.


---

