I will talk about several variations of the matching problem. One of them is as follows.
Suppose we have a graph $G=(V,E)$ and a partition $V_1 \cup V_2 \cup \ldots \cup V_k$ of $V$. We would like to find such a maximum cardinality matching $M$ of $G$
in which roughly the same number of vertices of each $V_i$ are matched. More formally,
we want to find such a maximum cardinality matching $M$, called {\bf balanced matching} that minimises $max\{|s_M(V_i)-s_M(V_j)|: 1 \leq i<j \leq k\}$,
where $s_M(V_i)$ denotes the number of vertices of $V_i$ matched in $M$. I'll show an algorithm that computes a balanced matching via LM-partition matchings.
In the {\bf LM-partition matching problem} we are given besides the graph and the partition of $V$ two parameters for each $i, 1 \leq i \leq k$: $l_i$ and $m_i$ and we wish to find an {\bf LM-partition matching} which is such matching $M$ of $G$, that for each $i$ the number of vertices of $V_i$ matched in $M$ is at least $l_i$ and
at most $m_i$ or ascertain that it does not exist. One can notice that if $l_i=0$ for each $i$ and the given graph $G$ is bipartite ($G=(A \cup B, E))$ and each vertex set of the partition of $V$ is either a subset
of $A$ or a subset of $B$, then an LM-partition matching is the intersection of two matroids. We will not make use of matroids. |