<p>That constraint is linear, so the entire problem is an instance of linear programming, thus can be solved in polynomial time.  (I am assuming there is no restriction or requirement for integer flows.)</p>

<p>In general if you allow arbitrary constraints, the problem can become NP-hard.</p>

CC BY-SA 4.0
2020-01-22T00:26:10.663Z
Actually I was implicitly thinking of integral flows [I am modelling another problem into this]. Thank you none the less! I'll edit the question.
user3508551
CC BY-SA 4.0
2020-01-21T08:29:37.817Z
2020-01-21T08:29:37.817Z
D.W.
<p><strong>Lemma 1.</strong> <em>The problem (assuming integer flow is required) is NP-hard.</em></p>

<p><em>Proof sketch.</em>  The proof is by reduction from 3D-matching.  The reduction is similar to the reduction for <em>equal flow</em> referred to in @JeffE's answer to <a href="https://cstheory.stackexchange.com/questions/17069/max-flow-with-conditional-edges?rq=1">this cstheory.stackexchange post</a>.</p>

<p>Fix a 3D-matching input <span class="math-container">$(X, Y, Z, E)$</span>. Recall that <span class="math-container">$X$</span>, <span class="math-container">$Y$</span>, and <span class="math-container">$Z$</span> are disjoint, with <span class="math-container">$|X|=|Y|=|Z|$</span> and <span class="math-container">$E\subseteq X\times Y \times Z$</span>, and the problem is to determine whether there is any subset <span class="math-container">$M$</span> of <span class="math-container">$E$</span> such that each element <span class="math-container">$e\in X\cup Y\cup Z$</span> occurs in exactly one triple in <span class="math-container">$M$</span> (in which case <span class="math-container">$M$</span> is called a <em>3D matching</em>).  Given <span class="math-container">$(X, Y, Z, E)$</span>, the reduction outputs the instance of the problem in the post specified by <span class="math-container">$s$</span>-<span class="math-container">$t$</span> flow network <span class="math-container">$G=(V, E)$</span> and set <span class="math-container">$S$</span>, defined as follows.  </p>

<p>Let <span class="math-container">$E=\{(x_1, y_1, z_1), (x_2, y_2, z_2), \ldots, (x_m, y_m, z_m)\}$</span> and <span class="math-container">$n=|X|=|Y|=|Z|$</span>.  Introduce source vertex <span class="math-container">$s$</span> and sink <span class="math-container">$t$</span>.  For each element <span class="math-container">$e$</span> of <span class="math-container">$X\cup Y \cup Z$</span>, introduce an "element" vertex <span class="math-container">$u(e)$</span> and capacity-1 edge <span class="math-container">$(s, u(e))$</span>.  For each triple <span class="math-container">$(x_i, y_i, z_i)$</span>, introduce a "triple" gadget consisting of "triple" vertices <span class="math-container">$w_0(i), w_1(i), w_2(i)$</span>, and capacity-1 edges <span class="math-container">$(u(x_i), w_0(i))$</span>, <span class="math-container">$(u(y_i), w_0(i))$</span>, <span class="math-container">$(u(z_i), w_1(i))$</span>, <span class="math-container">$(s, w_1(i))$</span>, capacity-2 edges <span class="math-container">$(w_0(i), w_2(i))$</span>, <span class="math-container">$(w_1(i), w_2(i))$</span>, and capacity-4 edge <span class="math-container">$(w_2(i), t)$</span>. </p>

<p>The picture below shows one triple gadget. It doesn't show the capacity-1 edges from <span class="math-container">$s$</span> to each element vertex <span class="math-container">$u(\cdot)$</span>.</p>

<p><a href="https://i.sstatic.net/kVzHK.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/kVzHK.png" alt="enter image description here"></a></p>

<p>Make <span class="math-container">$S$</span> contain all triple vertices <span class="math-container">$w_0(i), w_1(i), w_2(i)$</span> for all <span class="math-container">$i$</span>. That completes the reduction.  Note that in any integer flow respecting the <span class="math-container">$S$</span>-constraints, within each triple gadget as shown above, either all edges are saturated, or all edges have no flow.</p>

<p>We'll show that there is a 3D-matching <span class="math-container">$M$</span> if and only if there is an integer <span class="math-container">$s$</span>-<span class="math-container">$t$</span> flow of value <span class="math-container">$4n$</span> that respects the <span class="math-container">$S$</span>-constraints.</p>

<p>First assume there is a 3D-matching <span class="math-container">$M$</span>.  From <span class="math-container">$M$</span>, a corresponding flow <span class="math-container">$f$</span> can be obtained as follows.  For each element <span class="math-container">$e\in X\cup Y\cup Z$</span>, send one unit of flow from <span class="math-container">$s$</span> to <span class="math-container">$u(e)$</span>. For each triple <span class="math-container">$(x_i, y_i, z_i)\in M$</span>, saturate the edges in its triple gadget: send one unit of flow from <span class="math-container">$u(x_i)$</span> to <span class="math-container">$w_0(i)$</span>, one unit from <span class="math-container">$u(y_i)$</span> to <span class="math-container">$w_0(i)$</span>, one unit from <span class="math-container">$u(z_i)$</span> to <span class="math-container">$w_1(i)$</span>, one unit from <span class="math-container">$s$</span> to <span class="math-container">$w_1(i)$</span>, two units from <span class="math-container">$w_1(i)$</span> to <span class="math-container">$w_2(i)$</span>, two units from <span class="math-container">$w_1(i)$</span> to <span class="math-container">$w_2(i)$</span>, and four units from <span class="math-container">$w_2(i)$</span> to <span class="math-container">$t$</span>.  </p>

<p>By inspection the flow is integral and satisfies all conservation and capacity constraints. It has value <span class="math-container">$4n$</span> because it sends one unit from <span class="math-container">$s$</span> to each of the <span class="math-container">$3n$</span> element vertices, and one unit from <span class="math-container">$s$</span> to <span class="math-container">$w_1(i)$</span> for each of the <span class="math-container">$n$</span> triples <span class="math-container">$(x_i, y_i, z_i)$</span> in <span class="math-container">$M$</span>. And for each triple vertex <span class="math-container">$w_j(i)$</span> in <span class="math-container">$S$</span>, either both edges into <span class="math-container">$w_j(i)$</span> are saturated (and so have the same flow value), or neither have flow.  It follows that the flow respects the <span class="math-container">$S$</span> constraints.</p>

<p>Conversely, suppose there is a valid integer flow <span class="math-container">$f$</span> of value <span class="math-container">$4n$</span>. For each triple vertex <span class="math-container">$w_j(i)$</span> in <span class="math-container">$S$</span>, that vertex has two incoming edges, so by the <span class="math-container">$S$</span>-constraint both of those edges must have the same flow.  This and inspection of the triple gadget imply that, for each triple <span class="math-container">$i$</span>, either all the edges in the triple gadget are saturated, or none are. It follows that <span class="math-container">$f$</span> must have the form described in the previous paragraphs, corresponding to a 3D-matching. <span class="math-container">$~~~\Box$</span></p>

<p>It seems likely that the reduction (following the ideas in the reduction referred to in the post linked to above) can be strengthened so that there is a 3D-matching if and only if the flow network has an integer flow of <em>any positive value</em> (respecting <span class="math-container">$S$</span>).  It would follow that no poly-time approximation algorithm exists unless P=NP.</p>

CC BY-SA 4.0
2020-01-25T15:03:59.077Z
2020-01-26T16:20:25.907Z
2020-01-26T16:20:25.907Z
Neal Young
<p>What is known about the complexity of solving max flow with restrictions on individual flows for some nodes? </p>

<p>More precisely, in addition to wanting the max flow, you have a constraint for some vertices <span class="math-container">$S\subset V$</span> where <span class="math-container">$\forall s \in S, \forall u\in \{u | (u,s) \in E \} , f(u,s) \leq \frac{1}{2} \sum_{u} f(u,s) $</span></p>

<p>Meaning no one edge contributes more than half the total flow into a node. </p>

<p>Also, the flows must be integral [and the capacities are integral]</p>

<max-flow-min-cut><max-flow>
Max flow with restriction of individual flows
user3508551
# Max flow with restriction of individual flows

(Asked by: username_0 on 2020-01-21)

What is known about the complexity of solving max flow with restrictions on individual flows for some nodes?

More precisely, in addition to wanting the max flow, you have a constraint for some vertices $S\subset V$ where $\forall s \in S, \forall u\in \{u | (u,s) \in E \} , f(u,s) \leq \frac{1}{2} \sum\_{u} f(u,s) $

Meaning no one edge contributes more than half the total flow into a node.

Also, the flows must be integral [and the capacities are integral]

**Tags:** max-flow-min-cut, max-flow


---

## 2 answers

### Answer by username_1 on 2020-01-21. Score: 3

That constraint is linear, so the entire problem is an instance of linear programming, thus can be solved in polynomial time. (I am assuming there is no restriction or requirement for integer flows.)

In general if you allow arbitrary constraints, the problem can become NP-hard.

> **Comments:**
> **username_0**: Actually I was implicitly thinking of integral flows [I am modelling another problem into this]. Thank you none the less! I'll edit the question.  

---

### Answer by username_2 on 2020-01-25. Score: 2

**Lemma 1.** *The problem (assuming integer flow is required) is NP-hard.*

*Proof sketch.* The proof is by reduction from 3D-matching. The reduction is similar to the reduction for *equal flow* referred to in @JeffE's answer to [this cstheory.stackexchange post](https://cstheory.stackexchange.com/questions/17069/max-flow-with-conditional-edges?rq=1).

Fix a 3D-matching input $(X, Y, Z, E)$. Recall that $X$, $Y$, and $Z$ are disjoint, with $|X|=|Y|=|Z|$ and $E\subseteq X\times Y \times Z$, and the problem is to determine whether there is any subset $M$ of $E$ such that each element $e\in X\cup Y\cup Z$ occurs in exactly one triple in $M$ (in which case $M$ is called a *3D matching*). Given $(X, Y, Z, E)$, the reduction outputs the instance of the problem in the post specified by $s$-$t$ flow network $G=(V, E)$ and set $S$, defined as follows.

Let $E=\{(x\_1, y\_1, z\_1), (x\_2, y\_2, z\_2), \ldots, (x\_m, y\_m, z\_m)\}$ and $n=|X|=|Y|=|Z|$. Introduce source vertex $s$ and sink $t$. For each element $e$ of $X\cup Y \cup Z$, introduce an "element" vertex $u(e)$ and capacity-1 edge $(s, u(e))$. For each triple $(x\_i, y\_i, z\_i)$, introduce a "triple" gadget consisting of "triple" vertices $w\_0(i), w\_1(i), w\_2(i)$, and capacity-1 edges $(u(x\_i), w\_0(i))$, $(u(y\_i), w\_0(i))$, $(u(z\_i), w\_1(i))$, $(s, w\_1(i))$, capacity-2 edges $(w\_0(i), w\_2(i))$, $(w\_1(i), w\_2(i))$, and capacity-4 edge $(w\_2(i), t)$.

The picture below shows one triple gadget. It doesn't show the capacity-1 edges from $s$ to each element vertex $u(\cdot)$.

[![enter image description here](https://i.sstatic.net/kVzHK.png)](https://i.sstatic.net/kVzHK.png)

Make $S$ contain all triple vertices $w\_0(i), w\_1(i), w\_2(i)$ for all $i$. That completes the reduction. Note that in any integer flow respecting the $S$-constraints, within each triple gadget as shown above, either all edges are saturated, or all edges have no flow.

We'll show that there is a 3D-matching $M$ if and only if there is an integer $s$-$t$ flow of value $4n$ that respects the $S$-constraints.

First assume there is a 3D-matching $M$. From $M$, a corresponding flow $f$ can be obtained as follows. For each element $e\in X\cup Y\cup Z$, send one unit of flow from $s$ to $u(e)$. For each triple $(x\_i, y\_i, z\_i)\in M$, saturate the edges in its triple gadget: send one unit of flow from $u(x\_i)$ to $w\_0(i)$, one unit from $u(y\_i)$ to $w\_0(i)$, one unit from $u(z\_i)$ to $w\_1(i)$, one unit from $s$ to $w\_1(i)$, two units from $w\_1(i)$ to $w\_2(i)$, two units from $w\_1(i)$ to $w\_2(i)$, and four units from $w\_2(i)$ to $t$.

By inspection the flow is integral and satisfies all conservation and capacity constraints. It has value $4n$ because it sends one unit from $s$ to each of the $3n$ element vertices, and one unit from $s$ to $w\_1(i)$ for each of the $n$ triples $(x\_i, y\_i, z\_i)$ in $M$. And for each triple vertex $w\_j(i)$ in $S$, either both edges into $w\_j(i)$ are saturated (and so have the same flow value), or neither have flow. It follows that the flow respects the $S$ constraints.

Conversely, suppose there is a valid integer flow $f$ of value $4n$. For each triple vertex $w\_j(i)$ in $S$, that vertex has two incoming edges, so by the $S$-constraint both of those edges must have the same flow. This and inspection of the triple gadget imply that, for each triple $i$, either all the edges in the triple gadget are saturated, or none are. It follows that $f$ must have the form described in the previous paragraphs, corresponding to a 3D-matching. $~~~\Box$

It seems likely that the reduction (following the ideas in the reduction referred to in the post linked to above) can be strengthened so that there is a 3D-matching if and only if the flow network has an integer flow of *any positive value* (respecting $S$). It would follow that no poly-time approximation algorithm exists unless P=NP.


---

