Maximum weight matching in bipartite graphs with constraints

Question

Assume that we have two sets: A=(a_1,a_2,...,a_m) and B=(b_1,b_2,...,a_n) (Not necessarily of same size). A function F assigns a weight to each link from set A to set B: F:A*B->R. So, for example, F(a_1,b_1)=2 means that the weight of the link between a_1 and b_1 is 2. The problem is to connect the elements of set A to those of set B in order to maximize the sum of the link weights satisfying these constraints:

• The elements of set A must be matched to exactly one element of set B.
• Elements of set B are allowed to have zero or more matching (0,1,2...) although a constraint on the sum of weights C_i exists for the elements of B. That is, if we choose to connect a_1 to b_1, and a_2 to b_1, the sum of weights F(a_1,b_1)+F(a_2,b_1) should be less than or equal to C_1. This constraint is there for all elements of B.

I have searched for some ideas and I looked into the assignment problems and the Hungarian algorithm. The additional thing is that none of these consider the second constraint I have. Do you have any ideas on how to solve this?

Thanks

Answer 1

It's NP-hard.

Take a subset-sum instance {x₁, x₂, ..., x_n}, where x_i > 0 and a number k. Create a bipartite graph where left vertices are {a₁, ..., a_n}, right vertices are {b₁,b₂}, and:

F(a_i, b₁) = x_i

F(a_i, b₂) = 0

C₁ = k

C₂ = 0

So you can take the number x_i by connecting a_i with b₁, and leave it by connecting with b₂. Obviously there is a weight k matching iff the subset sum instance has a solution.