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)

Reference

  • slides
CATALOG
  1. 1. Network Flow ref
    1. 1.1. Limiation of Network Flow
    2. 1.2. Max-flow
      1. 1.2.1. Residual Graph Gf
        1. 1.2.1.1. Augmenting Path 增广路径
      2. 1.2.2. Cuts check
        1. 1.2.2.1. Cuts Capacity
      3. 1.2.3. Min Cut
        1. 1.2.3.1. Cuts and Flow
        2. 1.2.3.2. Max-flow, Min-cut theorem
      4. 1.2.4. Ford-Fulkerson Algorithm
        1. 1.2.4.1. Runtime Complexity
      5. 1.2.5. Edmonds-Karp Algorithm
        1. 1.2.5.1. Runtime Complexity
      6. 1.2.6. Capacity-Scaling Algoritm
        1. 1.2.6.1. Runtime Complexity
    3. 1.3. Network Flow Problems - S-T Flow 源匯流
    4. 1.4. Circulation with Demands - Flow 循環流
      1. 1.4.0.1. Steps:
    5. 1.4.1. Circulation with Demands and lower Bounds
      1. 1.4.1.1. Steps:
  • 2. Reference