Consider the following variant of the max-flow problem. We are given a set of flows and a network modelled by a graph. Each edge of the graph can accept only a subset of flows, which is different from the classical max-flow setting where each edge can accept all flows. I seek to design a max-flow algorithm in this situation and would like to have some hints.
$\begingroup$ $\endgroup$
8 
- 4$\begingroup$ What do you mean by subset of flows? How is it specified? I suspect this is np-complete, but you need to add details exactly what the inputs of your problem are. $\endgroup$Per Alexandersson– Per Alexandersson2025-03-07 16:58:56 +00:00Commented Mar 7 at 16:58
- $\begingroup$ Are you requiring that two distinct paths from source to sink, each with positive flow, have no common edges? $\endgroup$Nick S– Nick S2025-03-07 17:12:44 +00:00Commented Mar 7 at 17:12
- $\begingroup$ @PerAlexandersson Suppose there are 2 flows. Some edges can only support flow 1, i.e., flow 2 cannot use these edges. Some edges can only support flow 2, while others can support both flows. My input is the flows and the graph (as well as the flows supported by each edge), my problem is to solve the standard multiple-commodity max-flow or min-csot flow but under the above constraint. $\endgroup$lchen– lchen2025-03-08 02:38:48 +00:00Commented Mar 8 at 2:38
- $\begingroup$ @NickS I do not impose such constraint. $\endgroup$lchen– lchen2025-03-08 02:39:32 +00:00Commented Mar 8 at 2:39
- $\begingroup$ Does your standard multicommodity max flow problem allow upper bounds on flow variables? $\endgroup$RobPratt– RobPratt2025-03-08 02:58:44 +00:00Commented Mar 8 at 2:58
| Show 3 more comments
1 Answer
$\begingroup$ $\endgroup$
4 A standard multicommodity flow problem has nodes $i\in N$, supplies or demands $b_i$, arcs $(i,j)\in A$, arc capacities $u_{ij}$, commodities $k\in K$, arc-commodity capacities $u_{ijk}$, flow variables $x_{ijk}$, and constraints \begin{align} \sum_{k\in K} x_{ijk} &\le u_{ij} &&\text{for $(i,j)\in A$} \\ \sum_{(i,j)\in A} x_{ijk} - \sum_{(j,i)\in A} x_{jik} &= b_i &&\text{for $i\in N, k\in K$} \\ 0 \le x_{ijk} &\le u_{ijk} &&\text{for $(i,j)\in A, k\in K$} \end{align} Your variant is a special case in which some $u_{ijk}$ values are $0$, equivalently, some $x_{ijk}$ variables are fixed to $0$, equivalently, some $x_{ijk}$ variables do not appear in the problem.
- $\begingroup$ Thank you. This is the LP formulation. I am more interested in combinatorial approach with less complexity. $\endgroup$lchen– lchen2025-03-11 09:54:56 +00:00Commented Mar 11 at 9:54
- 2$\begingroup$ The point of the LP formulation is to show that this is a special case of the general problem, so any algorithm (combinatorial or otherwise) for the general problem applies. $\endgroup$RobPratt– RobPratt2025-03-11 12:24:35 +00:00Commented Mar 11 at 12:24
- $\begingroup$ Idid not get this point. SInce the constraint is particular in my context. How to apply existing combinatoiral multi-commodity flow algo in my case (not using LP)? Could you pls show an example? $\endgroup$lchen– lchen2025-03-14 02:20:09 +00:00Commented Mar 14 at 2:20
- $\begingroup$ Any multicommodity flow algorithm takes $N, A, K, b_i, u_{ij}, u_{ijk}$ as input. To solve your variant, pass in $u_{ijk}=0$ for all $i,j,k$ that are disallowed. $\endgroup$RobPratt– RobPratt2025-03-14 02:31:20 +00:00Commented Mar 14 at 2:31