Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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]
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.
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.
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)$.
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.
