3
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ The Linear Programming approach should be easy to modify to allow for this feature. $\endgroup$
    – usul
    Nov 6, 2019 at 21:56
  • $\begingroup$ could you please elaborate a bit more? $\endgroup$
    – karlosss
    Nov 6, 2019 at 22:41
  • $\begingroup$ 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. $\endgroup$
    – usul
    Nov 7, 2019 at 4:26

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – karlosss
    Nov 6, 2019 at 22:41
  • $\begingroup$ 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. $\endgroup$
    – Tassle
    Nov 6, 2019 at 22:45
  • $\begingroup$ Yup, seems like. Thanks! $\endgroup$
    – karlosss
    Nov 6, 2019 at 22:52
  • $\begingroup$ Cool, you're welcome :) $\endgroup$
    – Tassle
    Nov 6, 2019 at 22:58
  • $\begingroup$ @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. $\endgroup$
    – Tassle
    Nov 6, 2019 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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