2
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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$.

$\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.