The Art Gallery Guardian

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


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.


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

\displaystyle \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.


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).


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).

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