GNN Maximum Flow Problem (From Shusen Wang)

Maximum Flow Problem

ShusenWang 图数据结构和算法课程笔记 Slides

Maximum Flow Problem
- Description

在这里插入图片描述

Naive Algorithm
- Residual = Capacity - Flow
- Left: Original Graph
- Right: Residual Graph

在这里插入图片描述

- Bottleneck capacity = 2

在这里插入图片描述

- Iteration 2:
  - Find an augmenting path: s -> v_1 -> v_3 -> t
  - Update residuals

在这里插入图片描述

  - Remove saturated edge
- Iteration 3:
  - Find an augmenting path: s -> v_1 -> v_4 -> t
  - Update residuals

在这里插入图片描述

  - Remove saturated edge
- Iteration 4:
  - Cannot find an augmenting path: end of procedure
- Summay
  - Inputs: a weighted directed graph, the source 𝑠, and the sink 𝑡.
  - Goal: Send as much water as possible from 𝑠 to 𝑡
  - Constraints:
    - Each edge has a weight (i.e., the capacity of the pipe).
    - The flow must not exceed capacity.
  - naïve algorithm
    - Build a residual graph; initialize the residuals to the capacity. 
    - While augmenting path can be found: 
      - a. Find an augmenting path (on the residual graph.) 
      - b. Find the bottleneck capacity 𝑥 in the augmenting path. 
      - c. Update the residuals. (residual ← residual − 𝑥.)
  - The naïve algorithm can fail
    - The naïve algorithm always finds the blocking flow.
    - However, the outcome may not be the maximum flow.

Ford-Fulkerson Algorithm
- Problem with the naïve algorithm
- Procedure
- Worst-Case Time Complexity
- Summary
  - Ford-Fulkerson Algorithm
    - Build a residual graph; initialize the residuals to the capacities
    - While augmenting path can be found:
      - Find an augmenting path (on the residual graph.)
      - Find the bottleneck capacity 𝑥 on the augmenting path.
      - Update the residuals. (residual ← residual − 𝑥.)
      - Add a backward path. (Along the path, all edges have weights of 𝑥.)
  - Time complexity: 𝑂(𝑓⋅𝑚). (𝑓 is the max flow; 𝑚 is #edges.)
Edmonds-Karp Algorithm
- Procedure
  - Build a residual graph; initialize the residuals to the capacities.
  - While augmenting path can be found:
    - Find the shortest augmenting path (on the residual graph.)
    - Find the bottleneck capacity 𝑥 on the augmenting path.
    - Update the residuals. (residual ← residual − 𝑥.)
    - Add a backward path. (Along the path, all edges have weights of 𝑥.)
- Note: Edmonds-Karp algorithm uses the shortest path from source to sink. (Apply weight 1 to all the edges of the residual graph.)
- Time complexity: $O(m^2 \cdot n)$ . (m is #edges; n is #vertices.)
Dinic’s Algorithm
- Time complexity: $\cdot n^2)$ . (m is #edges; n is #vertices.)
- Key Concept: Blocking Flow
- Key Concept: Level Graph

在这里插入图片描述

- Procedure

在这里插入图片描述

  - On the level graph, no flow can be found!
  - End of Procedure

在这里插入图片描述

- Summary
  1. Initially, the residual graph is a copy of the original graph. 
  2. Repeat: 
    1. Construct the level graph of the residual graph. 
    2. Find a blocking flow on the level graph. 
    3. Update the residual graph (update the weights, remove saturated edges, and add backward edges.)
- Time complexity: $O(m \cdot n^2)$ . (m is #edges; n is #vertices.)

Minimum Cut Problem
- statement

在这里插入图片描述

  - Capacity (S, T) = sum of weights of the edges leaving S.
  - In the figure, three edges leave S.
    - Capacity (S,T) = 2 + 2 + 2 = 6

在这里插入图片描述

- Max-Flow Min-Cut Theorem
  - In a flow network, the maximum amount of flow from s to t is equal to the capacity of the minimum s-t cut.
  - In short, amount of max-flow = capacity of min-cut.

在这里插入图片描述

- Algorithm
  - Run any max-flow algorithm to obtain the final residual graph.
    - E.g., Edmonds–Karp        algorithm or Dinic’s algorithm.
    - Ignore the backward edges on the final residual graph
  - Find the minimum s-t cut (S,T) :
    - On the residual graph, find paths from source 𝑠 to all the other vertices.
    - S ← all the vertices that have finite distance. (Reachable from s.)
    - T ← all the remaining vertices. (Not reachable from s.)
- Example

在这里插入图片描述