Given a flow $f$ in graph $G$. For each node $v\in G$, we call the edges ajacent to $v$ containing non-zero quantity of flow as $v$'s active edges. My problem is to find a min-cost flow under the constraint that the number of active edges for each node $v$ is upper-bounded by a number $a_v$. I am looking for an efficient algorithm for this variant.
1 Answer
$\begingroup$
$\endgroup$
1
split every vertex $v$ into $v'$ and $v''$ and connect $v'$ to the incoming arcs and to $v''$, connect $v''$ to the outgoing arcs of $v$; set the flow constraints for $(v',v'')$ to $[0,a_v]$.
If all other flow constraints are $[0,1]$ then, because of the integrality of the mincost flow problem the constraints on the number of active arcs will be met.