# Bipartite Matching with a Partition Constraint over the Vertices

Let $$G = (X,Y,E)$$ be a bipartite graph and let $$X_1,\ldots,X_r$$ be a partition of $$X$$. For some $$i \in \{1,\ldots, r\}$$ and $$E' \subseteq E$$ we say that constraint $$X_i$$ is covered by some $$E'$$ if there are $$e \in E'$$ and $$x \in X_i$$ such that $$x$$ is an endpoint of $$e$$. Consider the problem of finding a matching $$M \subseteq E$$ such that all constraints $$i \in \{1,\ldots, r\}$$ are covered by $$M$$. In other words, we want to find a matching that is also a basis of the partition matroid $$X_1,\ldots,X_r$$ (with bounds one for each set).

Is this problem known to be NP-Hard? in general, this problem seems very natural, was it studied before (perhaps under a different notation)?

Thanks!

• (i) You mean "$e\in E'$" in instead of $e\in M$? (ii) So the problem is just to find a matching such that every $X_i$ has a matched vertex? (iii) Isn't this in P by reduction to max flow? Or for that matter just contract each $X_i$ to a single node and ask for a matching (that matches every vertex on the left-hand side) in the contracted graph? Apr 15 at 12:34
• Yes, you seem to be correct, thanks!
– John
Apr 15 at 17:30
• You can also look at matroid matching as a very general model of interest. See notes Michel Goemans or search. math.mit.edu/~goemans/18438F09/lec15.pdf Apr 15 at 17:50