# Number of edges in acyclic flow

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

Theorem1Main Theorem

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

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

Theorem2

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\leq 2(n/d)^2$$ and $$v\leq 2 m/d$$.

Proof

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\leq 2(n/d)^2$$. Similarly, we can also distribute the number of edges in between every two partitions, and get $$v\leq 2m/d$$.

Theorem3

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

Proof

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

$\sum_{i=1}^v n\sqrt{2}/\sqrt{i} = O(n\sqrt{v})$

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

ProofMain theorem

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(n\sqrt{v})$$ edges.

Corollary4

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

Proof

There exist $$\lambda(s,t)$$ $$st$$-edge disjoint paths with total length $$O(\sqrt{\lambda(s,t)}n)$$. The average length is $$O(\frac{n}{\sqrt{\lambda(s,t)}})$$. The $$k$$ shortest paths has total length $$O(k\frac{n}{\sqrt{\lambda(s,t)}})=O(k\frac{n}{\sqrt{k}}) = O(\sqrt{k}n)$$.

# References

[1] D.R. Karger, M.S. Levine, Finding maximum flows in undirected graphs seems easier than bipartite matching, Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing - STOC ’98. (1998) 69–78 10.1145/276698.276714.

Posted by Chao Xu on 2014-11-11.
Tags: Flow.