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)?


  • 2
    $\begingroup$ (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? $\endgroup$
    – Neal Young
    Apr 15 at 12:34
  • $\begingroup$ Yes, you seem to be correct, thanks! $\endgroup$
    – John
    Apr 15 at 17:30
  • 1
    $\begingroup$ 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 $\endgroup$ Apr 15 at 17:50


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.