# 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 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.

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.

• Is this considering the weights in the original graph? Commented Jan 15 at 20:00
• @Lozan Yes, it is considering the weights. As mentioned already: "Then the edge $(a,b)$ has unit weight if $x_i \in S$, else it has weight $0$." Commented Jan 15 at 23:42