0
$\begingroup$

I would like to find a solution for a max-flow problem where there is a combined capacity constraint on edges. For example, in the image below, the capacity for edge (1,3) and edge (2,3) should be 1 in total (which means in the max flow, there will be flow through only one of the edges). Any suggestion on what algorithms may solve this problem?
Thanks

enter image description here

$\endgroup$
2
$\begingroup$

Ok! I have i an idea, I don't know if it works. So in your example, you want to restrict the total capacity of $(1,3)$ and $(2,3)$ to be $1$. Then create a new vertex $4$, connect $4$ to $3$ with capacity $1$ and connect $1$ and $2$ to $4$ with each capacity $1$ like in the following picture then bingo!

enter image description here

And in general,if you want to restrict the capacity going into a vertex $v$, you can create a dummy vertex $u$ and connect $u$ to $v$ with the restrict capacity. Then you can ask all vertices connected to $v$ to connect to $u$ instead with their respective capacities. Then of course, you apply Ford–Fulkerson algorithm How's that?

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

In some special cases, which include your example, this can be handled efficiently by adding a dummy vertex and channelling the linked edges through it.

In full generality, max flow can be formulated as a linear programming problem. This allows arbitrary linear inequalities on the flows through a set of edges, but loses the ability to solve the problem in polynomial time.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.