Largest number of disjoint subsets of certain cardinality in bipartite graph such that every vertex is matched

119 Views Asked by At

Given a bipartite graph $G=(V,E)$, where $V$ is partitioned into $A$ and $B$, how can I design an algorithm that runs in polynomial time, such that given a positive integer $n\in\mathbb{N}$, the algorithm outputs the number $j$ that equals the largest number of disjoint subsets $A_1, \ldots, A_j$ of $A$ satisfying $|A_i|=n$ and $G$ has a matching in which every vertex of $A_i$ is matched?

To approach this problem, I set a matroid $(A, I_n)$ with ground set $A$ and where $I_n:=\{A_n\subseteq A, |A_n|\leq n : G \textrm{ has a matching in which every vertex of }A_n\textrm{ is matched}\}$.

I already proved that this defines a matroid. To output a set of subsets of $A$ of cardinality $n$ such that every vertex is matched in polynomial time, we can look at the intersection of the matroids $(A, I_{n-1})$ and $(A, I_n)$ and take the sets that belong to $I_n\setminus (I_n\cap I_{n-1})$. We know that such sets can be found in polynomial time because we intersect two matroids.

But I do not know how to find disjoint sets that satisfy this property, let alone the maximum number of them. I have thought about doing a disjoint union of the matroids $(A, I_n)$, and then somehow intersect them to find disjoint sets, but since the intersection of two matroids is in general not a matroid, I do not know how I could proceed.

Any suggestion is welcome.