Maximum flow with constraints

Question

In a flow network, suppose we add constraints of the following type:

The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$.

Is maximum-flow with such constraints still solvable in polynomial time?

Is it possible to reduce it to a standard maximum-flow problem?

NOTE: I found a recent paper that studies network flow with constraints, however, the constraints studied there are different:

"A negative disjunctive constraint states that a certain pair of arcs cannot be simultaneously used for sending flow"

"A positive disjunctive constraint forces that for certain pairs of arcs at least one arc has to carry flow".

Answer 1

First a quick note, the flow entering a vertex is equal to the flow leaving. I'll just refer to it as the amount of flow through a vertex.

Second, note that we can say $a \leq b \wedge b \leq a$, thus we can add the constraint $a = b$ for two vertices.

Then we can re-use the NP-hard result from the paper that you quoted:

"A negative disjunctive constraint states that a certain pair of arcs cannot be simultaneously used for sending flow"

The reduction is done by putting two proxy vertices in the middle of the respective arcs, let's call them $a$ and $b$.

We then also add two vertices $a'$ and $b'$, directly connecting to the source, and add the constraints $a = a'$ and $b = b'$. Finally we add vertex $c$, and connect it to $a'$, $b'$ and the sink. Note that the flow through $c = a' + b' = a + b$.

We finish the reduction by adding constraints $c \leq a$ and $c \leq b$. Now $a+b \leq a$ and $a+b \leq b$ implies that either $a=0$ or $b=0$ (or both).