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.
Add a comment |
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.
- $\begingroup$ thank you Manfred. $\endgroup$lchen– lchen2021-12-09 01:41:32 +00:00Commented Dec 9, 2021 at 1:41