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

  • $\begingroup$ You are right! Thanks. $\endgroup$ Commented Sep 4, 2020 at 11:37
  • 3
    $\begingroup$ 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. $\endgroup$ Commented Sep 4, 2020 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.