Bipartite matching with constraints on one part

Question

We have a bipartite graph with parts $A$ and $B$, and it is edge weighted. We have some constraints for part $B$. Each constraint is in this format: Between vertices $b_1$ and $b_2$ both from part $B$, at most one of them can be matched. The goal is to find the maximum weighted matching which qualifies these constraints.

Is it a famous problem? If yes, what is its name? Do you have any exact or approximation algorithms for it? If you know that it is NP-hard, can you reduce this problem to another famous NP-hard problem?

Generally, I want to know what has been done about this problem by previous computer scientists.

Answer 1

The problem is not approximable in polynomial-time within a factor of $n^{1-\varepsilon}$ for any constant $\varepsilon>0$, unless $\mathsf{NP} = \mathsf{ZPP}$.

To see this you can reduce from independent set. Let $G$ be of independent-set. Define $H$ as the graph that contains two-vertices $v_A, v_B$ for each vertex $v$ of $G$. For each edge $(u,v)$ of $G$, there is a constraint ``at most one of $u_B$ and $v_B$ can be matched''. All edges of $H$ weigh 1ドル$, and $H$ is bipartite (all vertices $v_A$ (resp. $v_B$) belong to $A$ (resp. $B$)).

Notice that $H$ has 2ドルn$ vertices, where $n$ is the number of vertices of $G$, and that $H$ has a constrained matching of weight at least $k$ if and only if $G$ has an independent set of size at least $k$ (the independent set consists of the matched vertices in $B$). The claim follows from the inapproximability of maximum independent-set (i.e., maximum of clique on the complementary graph).

• Soroush Vahidi: Thank you very much for your answer; however, as I have written in the statement, I want to know the work of others on this problem. Is it a famous problem that has a name? Has anyone tried to give an approximation algorithm for it by adding constraints to it or assessing it for a special group of graphs? Knowing the fact that it is NP-hard does not help me very much to know whether anyone before has explored this problem and have given a paper about it.
• Steven: Sorry, I'm not aware of this problem in the literature. What I wrote answers (in the negative) "Do you have any exact or approximation algorithms for it?" by showing that no approximation algorithms are likely to exist for essentially all interesting approximation factors.
• Soroush Vahidi: Even if an approximation algorithm exists for a particular group of graphs is helpful for me.