Tag Info

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