If I have a set of sources $S$ with total capacity $C$ and a set of sinks $T$ with the same capacity $C$, but not necessarily the same cardinality, is there an efficient way to find the minimum number of direct edges between sources and sinks and their required capacity, assuming $flow=C$?

TIA, Luis


1 Answer 1


Your problem is NP-hard. Consider a partition problem instance with input $a_1,\ldots,a_n$. We create a complete bipartite graph with $2$ source vertices each with capacity $\frac{1}{2} \sum_{i=1}^n a_i$, and $n$ sink vertices, where the $i$th vertex has capacity $a_i$. Each edge has infinite capacity.

It's easy to verify there is a partition with equal sum if and only if the solution to your problem on $G$ has $n$ edges.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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