Weighted Perfect Matching with Constraints on the Total Weight of Its Parts.

Under consideration is the following strongly NP-hard problem: Given a balanced complete bipartite graph with weights on the edges and a partition of one of its parts into nonempty and pairwise disjoint subsets, find a perfect matching of this graph such that the maximum total weight of edges of the matching incident to vertices of one subset of the partition is minimal. We propose some characterization of solutions for a special case of this problem in which, firstly, the weights of graph edges take values in , where is an integer greater than the number of edges of the unit weight; and, secondly, there is a perfect matching of the graph that consists of the edges only with weights and . Moreover, we identify the cases of problems that are polynomially solvable and strongly NP-hard. Finally, we show that if the number of subsets forming the partition of the special part of the graph is fixed then the problem is equivalent to finding a perfect matching of a given weight in an edge-weighted bipartite graph. [ABSTRACT FROM AUTHOR]