# Maximum one-to-many matching

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?

## 1 Answer

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\}$$.

• You are right! Thanks. Sep 4 '20 at 11:37
• You're welcome! Creating a problem instance with an obvious unique solution and then adding a "trap" (here, the edge $ae$) often finds counterexamples to greedy algorithms. Sep 4 '20 at 11:45