Encyclopedia

Circulation problem

Generalization of network flow problems

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated January 9, 2026

The circulation problem and its variants are a generalisation of network flow problems, with the added constraint of a lower bound on edge flows, and with flow conservation also being required for the source and sink (i.e. there are no special nodes). In variants of the problem, there are multiple commodities flowing through the network, and a cost on the flow.

01Definition

Given flow network $G(V,E)$ with:

$l(v,w)$ , lower bound on flow from node $v$ to node $w$ ,

$u(v,w)$ , upper bound on flow from node $v$ to node $w$ ,

$c(v,w)$ , cost of a unit of flow on $(v,w)$

and the constraints:

$l(v,w)\leq f(v,w)\leq u(v,w)$ ,

$\sum _{w\in V}f(u,w)=0$ (flow cannot appear or disappear in nodes).

Finding a flow assignment satisfying the constraints gives a solution to the given circulation problem.

In the minimum cost variant of the problem, minimize

$\sum _{(v,w)\in E}c(v,w)\cdot f(v,w).$

Multi-commodity circulation

In a multi-commodity circulation problem, you also need to keep track of the flow of the individual commodities:

$\,f_{i}(v,w)$	The flow of commodity $i$ from $v$ to $w$ .
$\,f(v,w)=\sum _{i}f_{i}(v,w)$	The total flow.

There is also a lower bound on each flow of commodity.

$\,l_{i}(v,w)\leq f_{i}(v,w)$

The conservation constraint must be upheld individually for the commodities:

$\ \sum _{w\in V}f_{i}(u,w)=0.$

02Solution

For the circulation problem, many polynomial algorithms have been developed (e.g., Edmonds-Karp algorithm, 1972; Tarjan 1987-1988). Tardos found the first strongly polynomial algorithm.

For the case of multiple commodities, the problem is NP-complete for integer flows. For fractional flows, it is solvable in polynomial time, as one can formulate the problem as a linear program.

Watch videos about Circulation problemExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Circulation problem”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

Circulation problem

01Definition

Multi-commodity circulation

02Solution

03Related problems

Sources and credits