I need to describe an algorithm that finds a maximum matching in a given undirected and unweighted graph. The runtime needs to be linear and is a 2-approximation, that is, the matching size (number of edges) should differ from a maximum matching size not more than a factor of two.

The problem I have is coming up with a linear-time algorithm. I know how to find a maximum matching, but this takes polynomial time.

  • 1
    $\begingroup$ What algorithm design paradigms have you tried? You might find that the algorithm is simpler than you have expected. $\endgroup$ – D.W. Oct 16 '16 at 0:59
  • $\begingroup$ cs.stackexchange.com/q/64915/755 $\endgroup$ – D.W. Oct 21 '16 at 17:01

Given an unweighted, undirected graph $G=(V,E)$ with $E = \{e_1, \dots, e_m\}$ being our edge set, $e_i = \{v,w\}$ with $v,w\in V$. Furthermore, we have $|E| = m$.

We can create a matching by adding edges greedily. This algorithm is linear in $m$, i.e. $O(m)$.

  1. M = $\emptyset$
  2. for each edge $e_i \in E$
    1. if $M \cup e_i$ form a valid matching, add $e_i$ to $M$

You still need to show that the greedy algorithm above is a 2-approximation. Let $M$ be the solution of the above algorithm and let $M^*$ be the optimal solution. Show that $|M| \leq 2|M^*|$.


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.