Circulation problem

Solution

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.

Related problems

Below are given some problems, and how to solve them with the general circulation setup given above.

• Minimum cost multi-commodity circulation problem - Using all constraints given above.
• Minimum cost circulation problem - Use a single commodity
• Multi-commodity circulation - Solve without optimising cost.
• Simple circulation - Just use one commodity, and no cost.
• Multi-commodity flow - If ${\displaystyle K_i(s_i,t_i,d_i)}$ denotes a demand of ${\displaystyle d_i}$ for commodity ${\displaystyle i}$ from ${\displaystyle s_i}$ to ${\displaystyle t_i}$, create an edge ${\displaystyle (t_i,s_i)}$ with ${\displaystyle l_i(t_i,s_i)=u(t_i,s_i)=d_i}$ for all commodities ${\displaystyle i}$. Let ${\displaystyle l_i(u,v)=0}$ for all other edges.
• Minimum cost multi-commodity flow problem - As above, but minimize the cost.
• Minimum cost flow problem - As above, with 1 commodity.
• Maximum flow problem - Set all costs to 0, and add an edge from the sink ${\displaystyle t}$ to the source ${\displaystyle s}$ with ${\displaystyle l(t,s)=0}$, ${\displaystyle u(t,s)=}$∞ and ${\displaystyle c(t,s)=-1}$.
• Minimum cost maximum flow problem - First find the maximum flow amount ${\displaystyle m}$. Then solve with ${\displaystyle l(t,s)=u(t,s)=m}$ and ${\displaystyle c(t,s)=0}$.
• Single-source shortest path - Let ${\displaystyle l(u,v)=0}$ and ${\displaystyle c(u,v)=1}$ for all edges in the graph, and add an edge ${\displaystyle (t,s)}$ with ${\displaystyle l(t,s)=u(t,s)=1}$ and ${\displaystyle c(t,s)=0}$.
• All-pairs shortest path - Let all capacities be unlimited, and find a flow of 1 for ${\displaystyle v(v-1)/2}$ commodities, one for each pair of nodes.