• Amortized Analysis
  • Aggregate Method
  • Accounting Method
  • Potential Method
  • Fibonacci Heap
• Network Flow
  • max-flow min-cut theorem
  • Ford-Fulkerson Method
    • termination
    • optimality
    • complexity
  • Edmond Karp Algorthm
  • Dinic’s Algorithm
  • Push-Relabel Algorithm
  • Applications
    • Disjoint Paths
    • Maximum Matching
      • Bipartite Matching
      • Hall’s Theorem
      • Konig’s Theorem
      • Edmond Blossom Algorithm
    • Path Cover

Network Flow

Two major problems

• Finding Maximum Flow
• Finding a Minimum Cut

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

• $flow\le capacity(S,T)$
• flow leaving source is same as flow leaving cut which is $\le$ capacity of cut

Ford Fulkerson Method

• check this out: https://www.cs.williams.edu/~shikha/teaching/spring20/cs256/lectures/Lecture19.pdf

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

• max_flow is always a valid flow
  • the augmenting of the path ensures that in = out for all vertices
• max_flow is always an integer[^1]
  • bottleneck >= 1 for every iteration and since only finite flow can escape it will eventually terminate

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 $G_f$ 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,\log C$)

No. If max capacity is $C$ the algorithm can still take $\ge C$ iterations

• each edge weight takes $\log C$ bits to represent
• input size = $O(V\log V+E\log V+E\log C)$
• running time is exponential in size of $C$ but polynomial in the rest so its called pseudopolynomial
  • if the running time is polynomial in magnitude but not size of input parameter

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(V{E}^2)$

Dinic’s Algorithm

$O(V^{2}E)$ and reduces to $O(\sqrt{V}E)$ on bipartite graphs

• build level graph to choose edges that make progress towards the sink using BFS.
• If the sink was never reached while building the level graph then stop and return the max flow
• using only valid edges in the level graph do multiple DFSs from $s\to t$ until a blocking flow is reached.
• repeat

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

Push-Relabel Algorithm

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

• preflow: just push as much flow as you can
• excess: leads to excess obv
• height: raise height so that you can only push downhill

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(V^2)$ relabels and $O(V^3)$ pushes
2. if vertex $v$ has positive excess in preflow $f$ then there is a path $v\to s$ in the residual network $G_f$
   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 $\ast$ $2n$ relabels $\therefore O(n^2)$ 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(n^3)$ non-saturating pushes
7. Use a suitable data structure to get highest vertex in $O(1{)}^{\ast }$ amortized time

Sharper Analysis

you can get a sharper bound of $O(V^2\sqrt{E})$ on the algorithm. idk how

[1]: also applies to rational edge weights because you can just multiply to get rid of the denominator

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

• add source and sink and find maximum flow = maximum 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

• let $X$ be any set of left nodes and $f(X)$ be the set of their neighbours
• a matching contains all left nodes only when $\forall X\subseteq L,|X|\le |f(X)|$

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