Max Flow with aggregated edge capacities

Question

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

Answer 1

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!

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?

Answer 2

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.