2-approximation algorithm for Minimum Maximal Matching (MMM) problem

Question

I'm looking to find a 2-approximation algorithm (pseudocode) for the minimum maximal matching problem. I tried to find one but I did not manage. I want to use it to implement a program in java. Can anyone help in finding pseudocode for this problem?

Answer 1

There is an easy $2$-approximation algorithm for finding a minimum size maximal matching. Simply find any maximal matching. Note that a maximal matching $M$ can be found greedily. Initialize $M=\emptyset$. Add any edge $xy$ to $M$, and in $G -x-y$ search for another edge to add and recurse.

Let $m$ be the size of a minimum maximal matching. To show that this is a $2$-approximation, we must check that for every maximal matching $M$, $|M| \leq 2m$. To see this let $V(M)$ be the vertices covered by $M$. Every minimum maximal matching $M_0$ must cover at least half the vertices of $V(M)$, otherwise we can extend $M_0$ via an edge in $M$.