Relative vertex capacity in max flow algorithm

I am designing a network for a max flow and would appreciate the following feature:

Say there is a flow incoming to a vertex. I would like to consume some specified amount of that flow and let through the rest. Unlike vertex capacity, which says "let though at most N units of flow", I need to "let through everything but N units of flow".

An example:

• Vertex of relative capacity 10

• Incoming flow = 15. Outgoing flow will be 15 - 10 = 5.

• Incoming flow = 10. Outgoing flow will be 10 - 10 = 0.

• Incoming flow = 5. Outgoing flow will be 5 - 10, which is less than 0, so 0.

Does such a feature exist? And if yes, which edges/vertices/edge capacities do I need to add/remove/modify and how?

Thanks a lot!

For edge "consumptions" I believe the following approach should work: [I misread your question at first, but am leaving this part for the benefit of future people reading this]

Suppose you have some edge $u\rightarrow v$ with "consumption" $c$. Then you can model this by inserting a vertex $w$ in the middle to get $u\rightarrow w \rightarrow v$ and then add an edge $w\rightarrow t$ with capacity $c$, where $t$ is your sink. Then you have to ensure that your max-flow algorithm prioritizes pushing flow through $w\rightarrow t$ over $w\rightarrow v$. Thus this flow will be "consumed" as much as possible before going through the edge. I see two ways in which this can be done:

-
If your algorithm works by finding an augmenting path, make sure that this augmenting path goes through $w\rightarrow t$ rather than $w\rightarrow v$ if possible (i.e. if $w\rightarrow t$ is not saturated). Also make sure that this holds for the "reverse edges" (i.e prioritize taking flow away from $w\rightarrow v$ rather than $w\rightarrow t$). This should not be difficult to do, but depends on the exact implementation, and on your access to it.

-
Or you can use a max-flow min-cost algorithm and give a positive cost (say 1) to every edge except those of the $w\rightarrow t$ type (who receive a cost of 0).

Then to get the answer to your original problem just ignore all the $w\rightarrow t$ edges.

Now, for vertex $v$ with "consumptions" $c$ you can simply add an edge $v\rightarrow t$ with capacity $c$ and modify your algorithm in the same way.

If you don't care about the exact value of the flow through each edge but only the total max-flow, then you don't even need to change anything to the algorithm and can just use the returned value for the new graph as is.

StackExchange Computer Science Q#116776, answer score: 2