3
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ 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$. $\endgroup$
    – J.G
    Oct 10 '20 at 12:28
  • $\begingroup$ @J.G Thanks. Your example really helps! $\endgroup$
    – hxiao
    Oct 10 '20 at 12:45
  • 4
    $\begingroup$ 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. $\endgroup$ Oct 11 '20 at 7:27
  • 2
    $\begingroup$ 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". $\endgroup$ Oct 11 '20 at 22:38
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.