# Number of edges in acyclic flow

The graph in this post are simple graphs with unit edge capacity.

Let $G=(V,E)$ be a graph with $n$ vertices and $m$ edges, then an acyclic integer flow of value $v$ saturates $O(nv )$ edges.

Everything here is in the Karger and Levine’s paper[1], I’m writing this down for my own sake.

Let $d$ to be the distance of the shortest path between $s$ and $t$. Let $v$ to be the value of a $s$-$t$-flow, then $v≤2(n/d)_{2}$ and $v≤2m/d$.

Let $V_{i}$ to be the set of vertices with distance exactly $i$ from $s$. The maximum flow is clearly bounded by $∣V_{i}∣∣V_{i+1}∣$, as all flows has to go in between the two levels and the maximum number of edges in between happens when it is a complete bipartite graph. Notice in order to maximize this value, we have $∣V_{i}∣=n/d$. Hence $v≤2(n/d)_{2}$. Similarly, we can also distribute the number of edges in between every two partitions, and get $v≤2m/d$.

If we take shortest augmenting path successively in the residual graph to find a flow of value $v$, then we saturate $O(nv )$ edges.

$v≤2(n/d)_{2}$, thus $d≤n2 /v $. If we take the shortest path successively, we have the number of edges we use in each augmenting path is

$i=1∑v n2 /i =O(nv )$

For the above theorem, one might ask what happens if we use $v≤2m/d$ inequality instead. Then we get the sum of the length of all the augmenting paths we ever route is $O(mgm)$, pretty neat.

Let $f$ be an acyclic flow of value $v$ in $G$. Remove all edges outside $f$, and let the remaining graph be $G_{′}$. Consider use shortest augmenting path algorithm sending a flow of value $v$ in $G_{′}$. Notice this would produce $f$. Thus this shows $f$ has $O(nv )$ edges.

Let $G$ be a simple graph on $n$ vertices. There exist $λ(s,t)$ $st$-edge disjoint paths, such that the $k$ shortest paths has total of $O(k n)$ edges for all $k≤λ(s,t)$.

There exist $λ(s,t)$ $st$-edge disjoint paths with total length $O(λ(s,t) n)$. The average length is $O(λ(s,t) n )$. The $k$ shortest paths has total length $O(kλ(s,t) n )=O(kk n )=O(k n)$.