2
$\begingroup$

I'm trying to disprove the correctness of below greedy algorithm which tries to compute the maximum matching for a bipartite graph but I'm unable to come up with a counter-example to disprove it.

  1. Find an edge $(u,v)$ such that u is an unmatched vertex with minimum degree and v is an unmatched endpoint with minimum degree
  2. Add $(u,v)$ to matching $M$ and remove it from $G$. Mark $u$ and $v$ as matched.
  3. Repeat 1 and 2 until there are no more edges with both endpoints being unmatched.

Any help would be appreciated. The other posts related to bipartite matching uses a different greedy algorithm to above.

$\endgroup$
2
$\begingroup$

Start with an example where you have a perfect matching, but which also has some wrong edge that will ruin the perfect matching if you pick it. For example, a graph that looks like the picture below.

bad edge

We want the following things to happen:

  1. All the vertical edges are in the graph, forming a perfect matching.
  2. Except for the diagonal edge in the middle, all other edges of the graph (not shown) stay within the left half or the right half of the graph.
  3. For some reason, your algorithm picks the diagonal edge.

So just add enough edges (carefully) to this graph that the diagonal edge in the middle is the graph picked by the greedy algorithm, and you'll have the counter-example you want.

$\endgroup$
  • $\begingroup$ But in the above case, the algorithm wouldn't pick the diagonal edge right? As the degree of both the endpoints is 2 which is not the minimum degree vertices. $\endgroup$ – GraphTheory Nov 12 '17 at 4:00
  • $\begingroup$ Like I said, you now need to add more edges to the graph to force the algorithm to pick the diagonal edge. $\endgroup$ – Misha Lavrov Nov 12 '17 at 4:02
  • $\begingroup$ Thanks a lot. I was able to figure out an example by adding more edges. $\endgroup$ – GraphTheory Nov 12 '17 at 4:21

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.