0
$\begingroup$

I was shown an algorithm in a test for using minimum vertex coverage in bipartite graph to find maximum edge matching. It made a lot of sense to me and I failed to come up with an example that proves it wrong, so I'd be happy if you could help me understand its correctness:enter image description here

$\endgroup$
5
  • $\begingroup$ By a "coverage" do you mean a vertex cover? $\endgroup$
    – Misha Lavrov
    Feb 2 at 16:40
  • $\begingroup$ @MishaLavrov yes, sorry if that wasn't clear $\endgroup$
    – user3917631
    Feb 2 at 16:41
  • $\begingroup$ Do you know the "max-flow min-cut" theorem? $\endgroup$
    – Brian Borchers
    Feb 2 at 16:43
  • $\begingroup$ @BrianBorchers yes, and I'm aware of how to use it to find maximum matching. $\endgroup$
    – user3917631
    Feb 2 at 16:44
  • $\begingroup$ I deleted the tag "covering-spaces". See en.wikipedia.org/wiki/Covering_space $\endgroup$
    – Paul Frost
    Feb 2 at 16:45

1 Answer 1

Reset to default
1
$\begingroup$

Kőnig's theorem tells us that the number of edges in a maximum matching of a bipartite graph is equal to the number of vertices in a minimum vertex cover.

This immediately highlights one suspicious feature of the algorithm: we are not adding edges to $M$ at the same rate as we are removing vertices from $U$. More precisely:

  1. In step 1, we "use up" a single vertex of the vertex cover to add a single edge to the matching.
  2. In step 2, we "use up" two vertices of the vertex cover to add a single edge to the matching.
  3. In step 3, we throw away a vertex in the vertex cover without adding anything to the matching at all.

Therefore if step 2 or step 3 are ever used, then the size of $M$ at the end will be less than the size of $U$ at the beginning, and therefore by Kőnig's theorem the matching $M$ will not be optimal.

For a specific example, consider the following graph:

a  b  c     d  e  f
 \ | / \   / \ | /
  \|/   \ /   \|/
   x     y     z

The only minimum vertex cover here is $U = \{x,y,z\}$. One way the algorithm could be conducted using $U$ is to:

  • Begin by selecting $x \in U$, $c \notin U$, and applying step 1 of the algorithm, adding $(x,c)$ to the matching and removing $x,c$ from the graph.
  • Then, select $z \in U$, $d\notin U$, and apply step 1 of the algorithm again, adding $(z,d)$ to the matching and removing $z, d$ from the graph.
  • Then, we are stuck with nothing to do for $y$; we remove it from the graph using step 3 and stop.

This creates a matching of size $2$, but there are size-$3$ matchings such as $\{(a,x), (c,y), (d,z)\}$, so the algorithm's output is not optimal.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .