1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ You are right! Thanks. $\endgroup$ – Erel Segal-Halevi Sep 4 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$ – j_random_hacker Sep 4 at 11:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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