1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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 $\endgroup$
    – Steven
    May 7 '20 at 11:37
  • $\begingroup$ 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. $\endgroup$
    – kubci98
    May 7 '20 at 11:43
  • $\begingroup$ 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. $\endgroup$
    – kubci98
    May 7 '20 at 11:44
  • $\begingroup$ cs.stackexchange.com/q/116858/755 $\endgroup$
    – D.W.
    May 9 '20 at 21:26
2
$\begingroup$

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$.

$\endgroup$
4
  • $\begingroup$ 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)$")? $\endgroup$
    – 8nzmh0vmwb
    May 9 '20 at 10:59
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    May 9 '20 at 12:04
  • $\begingroup$ 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 $\endgroup$
    – 8nzmh0vmwb
    May 9 '20 at 13:08
  • $\begingroup$ 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]$. $\endgroup$
    – Steven
    May 10 '20 at 9:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.