# 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!

• The Linear Programming approach should be easy to modify to allow for this feature. – usul Nov 6 '19 at 21:56
• could you please elaborate a bit more? – karlosss Nov 6 '19 at 22:41
• The LP has a bunch of flow constraints of the form "total flow into v = total flow out of v". So I think you can just modify these constraints and leave everything else as is. – usul Nov 7 '19 at 4:26

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.

• I need a vertex to consume the flow, not an edge. Maybe it is too late in the night now, but I just cannot see how to use your approach here. – karlosss Nov 6 '19 at 22:41
• My bad, I misread that. To do that with vertices just use the same approach as for vertex capacities : replace every vertex $v$ by $v-\rightarrow w \rightarrow v+$ where all in-coming edges to $v$ get connected to $v-$ instead and all out-going edges from $v$ get connected to $v+$ instead. And $w$ works as in my answer. I'll edit my answer accordingly if that solves your problem. – Tassle Nov 6 '19 at 22:45
• Yup, seems like. Thanks! – karlosss Nov 6 '19 at 22:52
• Cool, you're welcome :) – Tassle Nov 6 '19 at 22:58
• @kalosss Actually I think you can simply add an edge $v\rightarrow t$ with capacity $c$ instead of splitting $v$ in two parts. Edited the answer accordingly. – Tassle Nov 6 '19 at 23:08