0
$\begingroup$

The problem is to prove that if $G$ has a perfect matching, then every greedy matching matches up at least half of the nodes.

It is problem 10.4.4 y Lovász, Discrete mathematics. I do not understand his solution to the problem, so I want to check if my argument could work.

The argument that I give is minimal. Consider the bipartite graph with the minimal greedy matching condition. It cannot be the graph where every vertex has degree one, because the greedy algorithm would match the perfect matching.

We have to consider the bipartite graph where in both partitions there are half of the nodes with degree two, and half of the nodes of degree one. This clearly has perfect matching, but the greedy matching could take half of the vertices. Any other bipartite graph with perfect matching is constructed addind edges to this bipartite graph.

$\endgroup$
  • $\begingroup$ The problem is badly missing context. What "Discrete mathematics"? (Lovasz-Vestergombi, in the version I have it, doesn't have problem 10.4.4.) Is $G$ bipartite? What is a greedy matching? $\endgroup$ – darij grinberg Dec 28 '16 at 10:50
5
$\begingroup$

I find your argument hard to understand, in particular I have no idea what a graph with the minimal greedy matching condition is (and search returns nothing).

However, here's another argument, perhaps you will find it easier to digest:

Consider an edge $\{u,v\}$ of the optimal matching $M_\text{opt}$. Then, because the greedy matching $M_\text{greedy}$ is maximal, at least one of $u$ and $v$ is matched in $M_\text{greedy}$, otherwise we could add $\{u,v\}$ to $M_\text{greedy}$. Thus, $M_\text{greedy}$ matches at least half of vertices incident to $M_\text{opt}$, that is, at least $\frac{1}{2}\cdot 2 \cdot |M_\text{opt}|$ vertices. However, to cover $|M_\text{opt}|$ vertices you need at least $\frac{1}{2}|M_\text{opt}|$ edges in $M_\text{greedy}$ to cover them.

I hope this helps $\ddot\smile$

$\endgroup$
  • 1
    $\begingroup$ Very good. I understand now the Lovász argument. The phrase minimal greedy matching condition I used it to refer only that the greedy matching can only cover half of the vertices in the graph. $\endgroup$ – user2820579 Aug 11 '15 at 17:27

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.