MaximumFlowProblem

MaximumFlowProblem refers to the problem of finding the largest feasible flow from a designated source to a designated sink in a directed network with edge capacities. The input is a graph G = (V, E) together with a nonnegative capacity function c on edges and two distinguished vertices: a source s and a sink t.

A flow f assigns to each edge (u, v) a value f(u, v) with 0 ≤ f(u, v) ≤ c(u, v). For every vertex v other than s and t, the flow conservation condition must hold: the sum of flows into v equals the sum of flows out of v. The value of a flow, denoted |f|, is the net flow out of s (equivalently, into t).

The maximum flow problem asks for a feasible flow that maximizes |f|. A fundamental result is the Max-Flow Min-Cut Theorem: the maximum flow value equals the capacity of the minimum s–t cut. An s–t cut is a partition of V into S and T with s ∈ S and t ∈ T; the cut capacity is the sum of capacities on edges from S to T.

Algorithmically, maximum flow problems are solved by augmenting-path methods. Ford-Fulkerson builds a residual graph and repeatedly augments along s–t paths until no augmenting path remains. Edmonds-Karp implements Ford-Fulkerson with BFS to select shortest augmenting paths, giving a polynomial bound of O(VE^2). More advanced algorithms include Dinic’s method with level graphs and blocking flows, and push-relabel approaches, which have competitive practical performance and strong theoretical guarantees.

Applications of the maximum flow problem include network routing, transportation planning, bipartite matching, and image segmentation via graph cuts.