Skip to main content
5 of 7
clarify
Lozan
  • 21
  • 2

Weighted bipartite maximum cost with a fixed number of vertices

Having a complete bipartite graph with parts $A$ and $B$, which is edge-weighted, is there a way to compute a subgraph maximizing the sum of all its weights and:

  1. Only a constant number $n$ of vertices from $A$ are used.
  2. An edge points to each of the vertices in $B$.

In essence, which nodes from $A$ and which remaining edges to remove from the complete bipartite graph to get a graph with the maximum possible sum of its weights satisfying constraints 1 and 2.

example

In the example above, $n=2$ and $w_1 + w_2 + w_3$ is the maximum sum of weights which satisfies the two constraints.

Lozan
  • 21
  • 2