<p>Let <span class="math-container">$G = (X,Y,E)$</span> be a bipartite graph and let <span class="math-container">$X_1,\ldots,X_r$</span> be a partition of <span class="math-container">$X$</span>.
For some <span class="math-container">$i \in \{1,\ldots, r\}$</span> and <span class="math-container">$E' \subseteq E$</span> we say that constraint <span class="math-container">$X_i$</span> is <em>covered</em> by some <span class="math-container">$E'$</span> if there are <span class="math-container">$e \in E'$</span> and <span class="math-container">$x \in X_i$</span> such that <span class="math-container">$x$</span> is an endpoint of <span class="math-container">$e$</span>.
Consider the problem of finding a matching <span class="math-container">$M \subseteq E$</span> such that all constraints <span class="math-container">$i \in \{1,\ldots, r\}$</span> are covered by <span class="math-container">$M$</span>. In other words, we want to find a matching that is also a basis of the partition matroid <span class="math-container">$X_1,\ldots,X_r$</span> (with bounds one for each set).</p>
<p>Is this problem known to be NP-Hard? in general, this problem seems very natural, was it studied before (perhaps under a different notation)?</p>
<p>Thanks!</p>

CC BY-SA 4.0
2024-04-15T12:34:31.487Z
(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?
Neal Young
CC BY-SA 4.0
2024-04-15T17:30:29.570Z
Yes, you seem to be correct, thanks!
John
CC BY-SA 4.0
2024-04-15T17:50:49.883Z
You can also look at matroid matching as a very general model of interest. See notes Michel Goemans or search. https://math.mit.edu/~goemans/18438F09/lec15.pdf
Chandra Chekuri
<np-hardness><matching><bipartite-graphs><covering-problems><matroids>
Bipartite Matching with a Partition Constraint over the Vertices
John
# Bipartite Matching with a Partition Constraint over the Vertices

(Asked by: username_0 on 2024-04-15)

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!

**Tags:** np-hardness, matching, bipartite-graphs, covering-problems, matroids
> **Comments:**
> **username_1**: (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?  
> **username_0**: Yes, you seem to be correct, thanks!  
> **username_2**: You can also look at matroid matching as a very general model of interest. See notes Michel Goemans or search. https://math.mit.edu/~goemans/18438F09/lec15.pdf  

---

## 0 answers

