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

在这里插入图片描述

- Summary1. 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

在这里插入图片描述