Weighted bipartite maximum cost with a fixed number of vertices

Question

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

1. Only a constant number $n$ of vertices from $A$ are used.
2. At most one 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.

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

Answer 1

The problem is $\mathsf{NP}$-hard by a reduction from Exact Cover by 3-Sets:

Instance: a set $X = \{ x_1,x_2,...,x_{3n}\}$ and a family $F = \{ ( x_{i_1}, x_{i_2}, x_{i_3}) \} $ of 3-elements subsets of $X$ (triples);
Question: Is there a subfamily $F'$ of $F$ such that every element in $X$ is contained in exactly one triple of $F'$.

To reduce it to your problem, the family $F$ corresponds to set $A$ such that each set in $F$ corresponds to a vertex in $A$. The set $X$ corresponds to set $B$ such that each element of $X$ corresponds to a vertex in $B$. Let $a \in A$ be the vertex corresponding to a set $S \in F$ and let $b \in B$ be the vertex corresponding to an element $x_i \in X$. Then the edge $(a,b)$ has unit weight if $x_i \in S$, else it has weight $0$.

It is easy to see the following claim:

Claim: There exists a feasible solution for $(X,F)$ if and only if the cost of the instance $(A,B)$ is $3n$ (which is maximum possible for the constructed instance).

Thus, the bipartite matching problem stated in the problem definition is $\mathsf{NP}$-hard.