Determine whether a flow can satisfy node demands in a directed acyclic graph

I have the following problem that I'm unsuccessfully trying to solve:

I have a directed graph with node demands. Unlike circulation with demands, these node demands do not "subtract" from the flow - the nodes merely demand that there would be a flow of strength k flowing through them. The graph is acyclic, however, it is not a tree - multiple routes exist from the higher to the lower nodes.

The question is, whether a flow of strength R can satisfy all of the nodes' demands. Of course, a flow with strength more than k can flow through a node with demand k. Also, there are no capacity limits in the input graph.

I need to reduce this problem to the max-flow problem. I have been trying to reduce it to Circulation with lower bounds and Circulation with demands, but unsuccessfully, as I am unable to find out a good way on how to somehow limit the flow in the nodes to be minimal while satisfying the demands and measuring it at the same time.

• Can you clarify your problem? Where is the flow coming from? Is there a source vertex $s$? Where does it go to? Is there a target vertex $t$? If this is the case and the edge capacities are unbounded, isn't the problem equivalent to that of deciding whether all nodes with a positive demand lie on a simple path from $s$ to $t$? This would be easy to solve May 7 '20 at 11:37
• There are s and t vertices, where source s is connected to every vertex that does not have any other incoming edges and sink t is connected to every vertex that does not have any outwards edges. May 7 '20 at 11:43
• Also there does not have to be one single path on which all vertices lie - you might have to divide a flow of strength R into multiple paths so that every vertex is satisfied. May 7 '20 at 11:44
• cs.stackexchange.com/q/116858/755
– D.W.
May 9 '20 at 21:26

Add a new source $$s'$$ and the edge $$(s', s)$$ with maximum and minimum capacity $$R$$.

For each vertex $$v$$ with demand $$d$$ do the following:

• Replace $$v$$ with two vertices $$v_1$$ and $$v_2$$.
• Replace all the former edges $$(u,v)$$ with $$(u, v_1)$$
• Replace all the former edges $$(v, u)$$ with $$(v_2, u)$$.
• Add the edge $$(v_1, v_2)$$ with minimum capacity $$d$$.

The problem is now equivalent to checking whether there exists a feasible flow in a network with minimum and maximum edge capacities.

This problem is well known and can be reduced to max-flow (see, e.g., "Balances and Pseudoflows" in the book Algorithms by Jeff Erickson).

Essentially, if $$D$$ is the sum of all the edges' minimum capacities:

• Add a new source vertex $$s^*$$ and a new target vertex $$t^*$$.
• Add the edge $$(s^*, s')$$ with maximum capacity $$+\infty$$.
• For each edge $$(u,v)$$ with minimum capacity $$c \neq 0$$ and maximum capacity $$C$$, add the edge $$(u, t^*)$$ with capacity $$c$$, the edge $$(s^*, v)$$ with capacity $$c$$, remove the minimum capacity from $$(u,v)$$, and change the maximum capacity of $$(u,v)$$ to $$C-c$$ (if $$C$$ was $$+\infty$$ then the new capacity is also $$+\infty$$).

• Check whether the maximum flow from $$s^*$$ to $$t^*$$ is equal to $$D$$.

• Thanks, however it's not fully clear which capacities should have the 'original' edges $(u,v)$ in the modified at the first step network $(u, v_1)$, $(v_2,u)$ - $[0, +\infty]$ ? If I've got it right, the 'additional' edges $(v_1, v_2)$, $(u_1, u_2)$ etc., will receive instead of the $[d, +\infty]$ the new capacities $[0, +\infty]$ ("remove the minimum capacity from $(u, v)$")? May 9 '20 at 10:59
• I think you got it right. All the edges in the original network have capacities $[0, +\infty]$. After the first phase, some of the edges had their endpoints changed (buy they keep their $[0, +\infty]$ capacity) while, for each vertex $v$ with minimum capacity $d$, the edge $(v_1,v_2)$ with capacity $[d,+\infty]$ is added. After the second phase, an edge $(u,v)$ with capacity $[c,C]$ is transformed into 3 edges: $(s^*,v)$ with capacity $[0,c]$, $(u,t^*)$ with capacity $[0,c]$, and $(u,v)$ with capacity $[0,C-c]$, if $C=+\infty$ this is $[0,C-c]=[0,+\infty]$. All minimum capacities are now $0$. May 9 '20 at 12:04
• Thanks for the great explanation! It's become almost clear - but just for the 'verification': the edge $(s^′, s)$ with the ($[R, R]$) capacity after the second phase will be split to the edges: 1. $(s^*, s^′)$ ($[0, R]$ capacity) // OK 2. $(s^′, s)$ ($[0, |R-R|=0]$ capacity) // confusing one 3. $(s, t^*)$ ($[0, R]$ capacity) // OK May 9 '20 at 13:08
• You mixed up $s$ and $s'$ in some edges. $(s', s)$ will be split into $(s^*, s)$ with capacity $[0,R]$, $(s', t^*)$ with capacity $[0, R]$, and $(s', s)$ with capacity $[0, 0]$ (you can even avoid adding this edge since it has capacity 0). It is not related to the transformation of $(s', s)$ but, a part of the other steps of the construction, you will also add the edge $(s^*, s')$ of capacity $[0, +\infty]$. May 10 '20 at 9:26