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

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

CC BY-SA 4.0
2018-05-27T05:33:48.190Z
2018-05-27T05:33:48.190Z
Chao Xu
<p>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$?</p>

<p>TIA, Luis</p>

<graph-theory><co.combinatorics><network-modeling><bipartite-graphs>
Total flow using minimum number of edges on a bipartite network
Luis
# Total flow using minimum number of edges on a bipartite network

(Asked by: username_0 on 2018-05-27)

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, username_0

**Tags:** graph-theory, co.combinatorics, network-modeling, bipartite-graphs


---

## 1 answers

### Answer by username_1 on 2018-05-27. Score: 4

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.


---

