0
$\begingroup$

I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.

They mention that the 2-approximation ratio is a lower bound. How is a maximal matching a lower bound? Does it mean that it is the lowest approximation value we can get compared to $\log n$ of the greedy algorithm that is polynomial?

The images below show the optimal vertex cover = 8 but and a maximal matching of 12.

Maximal matching in Dasgupta

I decided to find another matching which I later discovered is called a maximum matching from Wikipedia. Since a maximum matching is also a maximal matching, I assume that this the worst that we can get, a maximum matching of 16 vertices.

Maximum matching

How can one improve on the edges picked then? My 16 vertices versus the book's 12?

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $M$ be a maximal matching, that is, $M$ is a matching which is not contained in a larger matching. Note that $M$ need not be a maximum matching, which is a matching of maximal size.

If $M$ contains $m$ edges, then:

  1. Any vertex cover contains at least $m$ vertices.
    This is because any vertex covers at most one edge of the matching.

  2. There exists a vertex cover containing $2m$ vertices, namely, all vertices of the matching.
    Indeed, if the vertices of the matching $M$ do not form a vertex cover, then there is some edge $e$ which is not covered by the vertices of $M$, and so $M$ is contained in the larger matching $M \cup \{e\}$, contradicting the definition of $M$.

$\endgroup$

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.