A weighted perfect matching with constraints on weights of its parts

We consider the following strongly NP-hard problem. Given an edge–weighted balanced complete bipartite graph with a partition of its part into non-empty and pairwise disjoint subsets, the problem is to find a perfect matching of this graph such that maximum sum of weights of edges from the matching incident to vertices of a subset of the partition is minimum. We present a characterization of solutions of a special case of this problem, in which weights of graph edges take values from the set $\{0, 1, \Delta\},$ where $\Delta$ is an integer that is greater than the number of edges of the unit weight and there is a perfect matching of the graph that consists of edges with weights $0$ and $1$. Besides, we identify polynomially solvable and strongly NP-hard special cases of this problem. Finally, we show that if the number of subsets forming the partition is fixed then the considered problem is equivalent to the problem of finding a perfect matching of a given weight in an edge-weighted bipartite graph. Illustr. 5, bibliogr. 29.