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)G=(V,E) be a graph with nn vertices and mm edges, then an acyclic integer flow of value vv saturates O(nv)O(n\sqrt{v}) edges.

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

Theorem2

Let dd to be the distance of the shortest path between ss and tt. Let vv to be the value of a ss-tt-flow, then v2(n/d)2v\leq 2(n/d)^2 and v2m/dv\leq 2 m/d.

Proof

Let ViV_i to be the set of vertices with distance exactly ii from ss. The maximum flow is clearly bounded by ViVi+1|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 Vi=n/d|V_i|=n/d. Hence v2(n/d)2v\leq 2(n/d)^2. Similarly, we can also distribute the number of edges in between every two partitions, and get v2m/dv\leq 2m/d.

Theorem3

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

Proof

v2(n/d)2v\leq 2(n/d)^2, thus dn2/vd\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

i=1vn2/i=O(nv)\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 v2m/dv\leq 2m/d inequality instead. Then we get the sum of the length of all the augmenting paths we ever route is O(mlogm)O(m\log m), pretty neat.

ProofMain theorem

Let ff be an acyclic flow of value vv in GG. Remove all edges outside ff, and let the remaining graph be GG'. Consider use shortest augmenting path algorithm sending a flow of value vv in GG'. Notice this would produce ff. Thus this shows ff has O(nv)O(n\sqrt{v}) edges.

Corollary4

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

Proof

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

Posted by Chao Xu on .
Tags: Flow.