Vincec's Dimension

# Algorithm Review Notes - Network Flow

Word count: 624 / Reading time: 4 min
2018/11/25 Share # Network Flow ref

## Limiation of Network Flow

• Capacity Law(Constraints)
• O <= f(e) <= c(e)
• Conservation Law
• flow in = flow out
• sum(f(e in to v)) = sum(f(e out of v))

## Max-flow

Given a flow network G, find a flow f from s to t of the maximum possible value.

### Residual Graph Gf

• Forward Edges
• Backward Edges

Network: G = (V, E) and flow f
Residual capacity: cf(e) = c(e) - f(e)
Residual Graph: Gf(V, Ef), where Ef = {e| f(e) < c(e)}(forward edge){eR| f(e) > 0}(backward edge)

#### Augmenting Path 增广路径

Path in the Gf

Bottleneck(P, f): the smallest capacity in Gf on any edge of P.

### Cuts check

#### Cuts Capacity

cap(A, B) = sum of c(e out of A)

### Min Cut

• Minimum cut = the cut in the network that has the smallest possible capacity
• Minimum cut capacity = the capacity of the minimum cut

#### Cuts and Flow

• |f| = sum of (flow-out of A) - sum of (flow-in of A) = sum of f(e out of source)
• Maximum flow ≤ capacity of any cut
• Maximum flow = Capacity of the min. cut of the network

#### Max-flow, Min-cut theorem

Value of Maxi-flow = Capacity of the min-cut

• the construct yields a cut: S ∈ X, T ∉ X, there is T ∈ Y
• For each forward edge e in the cut C: f(e) = c(e)
• For each backward edge e in the cut C: f(e) = 0

### Ford-Fulkerson Algorithm

• Given(G, s, t, c) [Graph, source S, sink T, capacity]
• Start with |f| = 0, f(e) = 0, [set the start flow]
• Find an augmenting path, [by using dfs]
• Augment flow along this path
• Repeat until no an s-t path in the Gf, [by proving of min cuts, repeat times will exceed the edge number due to residual graph]

#### Runtime Complexity

• Total number of iterations: |f|
• Each augmentation increases value of flow by at least 1
• Running iterations: O(E + V)
• Total runtime: O(|f|*(E + V)), pseudo-polynomial, input size: |f|

### Edmonds-Karp Algorithm

By using BFS instead of DFS, Find an shortest augmenting path

#### Runtime Complexity

O(V*E2), polynomial

### Capacity-Scaling Algoritm

• The bottleneck capacity if an augmenting path is the minmum residual capacity of any edge in the path
• Choosing augmenting path with highest bottleneck capacity

#### Runtime Complexity

O(E2 ㏒|f|), weakly-polynomial, because the input size is ㏒|f|

## Network Flow Problems - S-T Flow 源匯流

• Bipartite Graph (translation problem)
• Rook Attack
• Edge Disjoint Paths (do not share any edge, but ok with same vertex)
• Edge Disjoint Paths in Undirected Graphs
• Vertex Disjoint Paths (do not share any vertex, edge either of casuse)
• Image Segmentation (to find the maximum, by using whole minus the min-cut)

## Circulation with Demands - Flow 循環流

Circulation (having s-t flow as well as t-s flow, used in supply and demand, to find a feasible) _[ref1][ref2] [ref3]_

• total supply(positive on the node) = total demand(negative on the node)
• capacity constraint (0 <= flow <= cap)
• demand constraint ( flow in - flow out = node demand)

#### Steps:

• Remove demands (By adding s-t)
• Calculate using FF
• replace demans (By removing s-t)

### Circulation with Demands and lower Bounds

Want to force flow have flow between two given nodes, need to change the Capacity Constraint with that lower bound, to find a feasible [ref4]:

• Capacity Constraint: l(e) <= f(e) <= c(e)

#### Steps:

• Remove Lower bound [lower, upper], by changing the each node demands
• L(v) = f0in(v) - f0out(v) = sum(l(e to v)) - sum(l(e out to v))
• compute L(node) • Remove demands (By adding s-t)
• Calculate using FF
• replace demands (By removing s-t)

• slides

Author: VINCEC