# Max-flow/min-cut to determine densest subgraph

I have been trying to understand how a maximum average degree problem can be solved as a maximum flow problem for my optimization class from this article: https://hal.archives-ouvertes.fr/inria-00504914/document. I don't understand this bit:

"Clearly, if $H ⊆ G$ is the densest subgraph in $G$, its $|E(H)|$ edges will send a flow of $2|E(H)|$ to their $|V (H)|$ vertices, such a flow being feasible only if $z ≥\frac{2|E(H)|}{|V (H)|}$. An elementary application of the max-flow/min-cut theorem, or of Hall’s bipartite matching theorem shows that such a value for $z$ is also sufficient."

$z$ is how much a vertex in $V(G)$ can absorb.

Would anyone like to explain this section? Particularly the max-flow/min-cut theorem application.

For any edge $e$ we put an additional vertex $v_e$ on it and direct the created par of sub-edges away from it. Now we pump in exactly $2$ units of flow through that vertex. Remember that the sub-edges are directed, so all that flow has to exit through the vertices of $V$.

Now, for any subgraph $H \subset G$ the total out-flow from $V$ has to be at least $2|E(H)|$, because each $v_e$ pumps in $2$ units of flow. Thus, whatever happens, the average outflow per vertex is at least $\frac{2|E(H)|}{|V(H)|}$. In other words, if we were to bound the out-flow of all vertices $v \in V$ by $z$, then for the flow to be possible, we have to have $z \geq \frac{2|E(H)|}{|V(H)|}$. In particular that has to be satisfied even if $H$ is the densest subgraph of $G$.

On the other hand, suppose that $z = \frac{2|E(H)|}{|V(H)|}$ where $H$ is the densest subgraph of $G$. Will this be enough to make such a flow possible? To check this, we instead upperbound the outflow from $v \in V$ by $z$, construct a maximum flow given the constraints, and see if it matches the $2|E(G)|$ value.

To see that it is indeed possible to construct such a flow, make $2$ copies of each $v_e$ and $z$ copies of each $v \in V$, and use cliques $K_{2,z}$ to connect all these copies. Now, check that the Hall's condition is satisfied, i.e., for any set of vertices corresponding to edges $v_e$, its set of neighbors is exactly the set of vertices of $V$ incident to the relevant edges. Because of how we picked $z$, the set of neighbors is always big enough. The matching gives you the flow. With some more work (eg. use fractional matchings), this will be true also if $z$ is not an integer.

I hope this helps $\ddot\smile$

• I appreciate you taking the time to answer, but I don't understand the last paragraph since I haven't done cliques. I actually haven't studied that much graph theory.
– Eva
Mar 31, 2016 at 16:22
• @Eva I just mean that if there is an edge between $v_e$ and some $v$, then you connect all the copies of $v_e$ to all the copies of $v$. Mar 31, 2016 at 16:59