information:classification, information:highlighting, information:filtering, information:extraction, linguistic:voice_change
Relation to other problems

A variation of this problem is to find a flow which is maximum, but has the lowest cost among the maximum flow solutions. This could be called a minimum-cost maximum-flow problem and is useful for finding minimum cost maximum matchings.

With some solutions, finding the minimum cost maximum flow instead is straightforward. If not, one can find the maximum flow by performing a binary search on d {\displaystyle d}.

A related problem is the minimum cost circulation problem, which can be used for solving minimum cost flow. The minimum cost circulation problem has no source and sink; instead it has costs and lower and upper bounds on each edge, and seeks flow amounts within the given bounds that balance the flow at each vertex and minimize the sum over edges of cost times flow. Any minimum-cost flow instance can be converted into a minimum cost circulation instance by setting the lower bound on all edges to zero, and then making an extra edge from the sink t {\displaystyle t} to the source s {\displaystyle s}, with capacity c (t, s) = d {\displaystyle c(t,s)=d} and lower bound l (t, s) = d {\displaystyle l(t,s)=d}, forcing the total flow from s {\displaystyle s} to t {\displaystyle t} to also be d {\displaystyle d}.

The following problems are special cases of the minimum cost flow problem (we provide brief sketches of each applicable reduction, in turn):