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

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