Network Flow

2026-11-18

Network Flow

Two major problems

Max-Flow Min-Cut Theorem

The maximum value of an s-t flow is equal to the minimum capacity over all s-t cuts.

https://www.youtube.com/watch?v=EGDokIJWrQU

Ford Fulkerson Method

def ford_fulkerson(G, s, t):
    G_f = residual_graph(G)
    f_e = 0 for e in G_f.e
    max_flow = 0
    while st_path = find_path(G_f):
        bottleneck = min_e(G_f) # min residual capacity
        # augment residual network
        for e in st_path.forward_e:
            e += bottleneck
        for e in st_path.reverse_e:
            e -= bottleneck 
        max_flow += bottleneck

Termination

terminates with a valid flow

Optimality

for any optimality problem

1. identify optimality conditions
2. design an algorithm that terminates with optimality conditions

Ford-Fulkerson Optimality Condition

if f is a flow in G such that the residual network Gf has no s−t path, then the f is a maximum flow

there is no augmenting path therefore there is no flow from T

and the algorithms necessarily terminates with this condition

Complexity

Running time is of the order O(EVC)

Does Ford-Fulkerson run in polynomial time in the size of the input (E,V,logC)

No. If max capacity is C the algorithm can still take ≥C iterations

Edmonds-Karp Algorithm

use BFS to find augmenting path. Why? Ford Fulkerson worst case occurs when every time your bottleneck is very small. For larger bottleneck you want to take fewer edges. BFS naturally will find shortest edge path and remove dependency on C for time complexity.

O(VE2)

Dinic's Algorithm

O(V2E) and reduces to O(VE) on bipartite graphs

  1. first iteration level graph
  2. second iteration level graph

Push-Relabel Algorithm

all you have: https://www.youtube.com/watch?v=0hI89H39USg

def push_relabel(G, source, sink):
    def push(v):
        bn = min(v.excess, cap(v, w)) # choose downhill vertice
        push bn units of flow along (v, w)
        
    def relabel(v):
        v.height = v.height + 1
        
    # init
    source.height = n # number of vertices
    v.height = 0 for v in G if v != source
    edge.f_e = edge.u_e for edge in source.outgoing_edges
    edge.f_e = 0 for edge in remaining_graph
    
    # main loop
    while v in G and v.excess != 0 and v != source:
        v = max_height(G_f) # vertex with max height
        if edge (v, w) with v.height = w.height + 1:
            push(v)
        else:
            relabel(v) 

Properties

  1. algorithm terminates after O(V2) relabels and O(V3) pushes
  2. if vertex v has positive excess in preflow f then there is a path v→s in the residual network Gf
    1. should be possible to undo excess
  3. every vertex has height at most 2n
    1. only relabeled when it has excess
    2. there is a path with atmost n−1 edges between v and s
    3. s.height=n always
    4. for v to push to s it must have decrements of 1 for n−1 edges
    5. thus max height<2n
  4. n vertices * 2n relabels ∴O(n2) relabels
  5. between two saturating pushes on the same edge each of (v, w) is relabeled at least twice
    1. this gives O(VE) bound on saturating pushes
  6. between two relabels there are at most n non-saturating pushes
    1. O(n3) non-saturating pushes
  7. Use a suitable data structure to get highest vertex in O(1)* amortized time

Sharper Analysis

you can get a sharper bound of O(V2E) on the algorithm. idk how

Applications

Disjoint Paths

Edge-Disjoint Paths

set of paths such that each edge appears in at most one path

Solution

maximum flow assuming capacity of each edge is 1

Node-Disjoint Paths

every node appears in at most one path

split every node into 2 with a edge between the two parts that acts as the limiter

Maximum Matchings

Find a maximum-size set of node pairs in an undirected graph such that each pair is connected with an edge and each node belongs to at most one pair

Bipartite Matching

Hall's Theorem

Hall's Theorem

Used to find out whether a bipartite graph has a matching that contains all left or right nodes. If the number of left and right nodes is the same, it tells us if it is possible to construct a perfect matching

Konig's Theorem

maximum matching = minimum vertex cover for bipartite graph

minimum vertex cover = smallest vertice set to touch every edge

Edmond's Blossom Algorithm

Maximum Matching in general graph: https://www.youtube.com/watch?v=3roPs1Bvg1Q

https://web.stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf

linked from


  1. also applies to rational edge weights because you can just multiply to get rid of the denominator↩︎