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[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

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

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.