<p>How can I limit the total flow for some edges in an directed graph. We know that every edge can have an upper and lower bound solely. But apart from this sole upper and lower bounds for each edge, if I want to put a limitation on the total flow of some selected edges what should I do? The problem is so that I can not define a dummy sink, make edges starting from selected vertexes to the that dummy sink then from there to previously connected vertexes.</p>

CC BY-SA 3.0
2017-05-20T15:37:51.520Z
Do you know about the LP-formulation of max-flow? You may simply add such a constraint (that bounds the total flow of some selected edges) to the LP.
Gamow
CC BY-SA 3.0
2017-05-21T04:01:29.953Z
Is there a transform that preserves integrality? the new LP-formulation might not be integral.
Chao Xu
CC BY-SA 3.0
2017-11-03T17:38:25.070Z
If you require the flow to be integral, then the problem is NP-hard.  Consider we have an uncapacitated graph. A subset has a capacity upper bound 1 implies only 1 of the edges can be used in the flow. This is the same as having conflict constraints. https://link.springer.com/chapter/10.1007/978-3-642-21527-8_34
Chao Xu
<graph-theory><network-modeling>
limit the total flow for some edges in an directed graph
Mehdi Tanhatalab
# limit the total flow for some edges in an directed graph

(Asked by: username_0 on 2017-05-20)

How can I limit the total flow for some edges in an directed graph. We know that every edge can have an upper and lower bound solely. But apart from this sole upper and lower bounds for each edge, if I want to put a limitation on the total flow of some selected edges what should I do? The problem is so that I can not define a dummy sink, make edges starting from selected vertexes to the that dummy sink then from there to previously connected vertexes.

**Tags:** graph-theory, network-modeling

> **Comments:**
> **username_1**: Do you know about the LP-formulation of max-flow? You may simply add such a constraint (that bounds the total flow of some selected edges) to the LP.  
> **username_2**: Is there a transform that preserves integrality? the new LP-formulation might not be integral.  
> **username_2**: If you require the flow to be integral, then the problem is NP-hard.  Consider we have an uncapacitated graph. A subset has a capacity upper bound 1 implies only 1 of the edges can be used in the flow. This is the same as having conflict constraints. https://link.springer.com/chapter/10.1007/978-3-642-21527-8_34  

---

## 0 answers

