1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ thank you Manfred. $\endgroup$
    – lchen
    Commented Dec 9, 2021 at 1:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .