Maximum one-to-many matching

Question

Let $G = (X+Y,E)$ be a bipartite graph and $k\geq 1$ an integer. A maximum $k$-matching is a subset of $E$ in which each vertex of $X$ is adjacent to at most $k$ edges and each vertex of $Y$ is adjacent to at most $1$ edge.

A maximum-cardinality $k$-matching can be found by the following algorithm:

• Create $k$ copies of each vertex $x\in X$, such that each copy is adjacent to all neighbors of $x$ in $Y$.
• Find a maximum matching in the resulting graph.

Its run-time complexity for a graph with $n$ vertices and $m$ edges, using the Hopcroft-Karp algorithm, is $O(k m\sqrt{k n}) =O(k^{3/2}\cdot m\sqrt{n})$.

I am interested in the following alternative algorithm:

• Repeat $k$ times:

  • Find a maximum matching in $G$.
  • Remove the matched vertices of $Y$ from the graph.

Its run-time complexity is $O(k \cdot m\sqrt{n})$.

But does this algorithm always find a maximum $k$-matching?

Answer 1

No. Here is a counterexample: $X=\{a,b\}, Y=\{c,d,e,f\}, E=\{ac, ad, ae, be, bf\}, k=2$. The first iteration of your algorithm could choose $\{ae,bf\}$ (in particular, the edge $ae$), preventing a solution from being found even though one does exist: $\{ac, ad, be, bf\}$.