Cheng: Graph - Network Flow Problems

Network Flow

in a finite directed graph (also called a network), each edge has a capacity and each edge receives a flow. Flow satisfies 2 constraints:

the amount of flow cannot exceed the capacity of the edge.
the amount of flow into a node equals the amount of flow out of it except source, which has only outgoing flow, or sink which has only incoming flow.

flow network can be used to model

traffic in a road system
circulation with demands
fluid in pipes
currents in an electrical circuit
etc

Max-Flow Problem: following network (from CLRS) has a maximum possible flow from source-0 to sink-5 is 23. how to find the max possible flow in a network?

Bipartite Matching Problem

Bipartite graph: each node has no edge for the same layer

Min-cost Cut Problem

Remove some edges from graph G such that there is no path from s to t after removing the edges (image destroy bridges with minimum cost)

Finding Max-Flow (Ford-Fulkerson Algorithm)

Ford-Fulkerson algorithm:

Start with 0 flow.
While there exists an augmenting path:
- find an augmenting path
- compute bottleneck capacity
- increase flow on that path by bottleneck capacity

* this FF algorithm description is very much simplified. To implement the algorithm, one has to understand concepts like: residual graph, forward edge, backward edge.

Questions:

how to find an augmenting path?
if FF terminates, does it always compute a max-flow?
Does FF always terminate? If so, after how many augmentations?

Min-cost Cut

This is a variant of max-flow problem. Basically, the problem says how to remove some edges with min-cost such that no path from s to t. For the network from CLRS book, the min-cost cut as follows:

solution

max-flow min-cut theorem says: (max flow) = (min-cut).

from above example, we know the max flow is 23, the min-cut is 12 + 7 + 4 = 23
CLRS book has proof about this theorem
sometimes min-cost cut also calls minimum s-t cut (s-t: source-terminal/sink)
similar to: (min vertex cover) = (max independent set), for a bipartite graph (Konig Theorem)

one can use FF algorithm to find max-flow, but how to find min-cost cut?
one answer is to use residual graph

run FF algorithm and consider the final residual graph
collect all reachable vertices from source (obviously, this set does not include t)
min-cost cut edges are those edges from reachable vertices to unreachable vertices

min-cost cut problem is different with min-cut problem mentioned in Randomized Algorithm

randomized min-cut problem is about undirected graph, this is about directed graph
randomized min-cut problem is cutting minimum number of edges of G to disconnect the graph. min-cost cut is about disconnecting s-t, and is about min-cost of edges not about edge numbers.

min-cut problem is much harder than min-cost cut problem discussed here!

[TODO] Min-cost Max-flow

finding a cheapest possible way of sending a mount of flow through a network.

Bipartite Matching

BFS and Bipartite testing

Cheng

2015-11-01

Graph - Network Flow Problems