Find a maximum matching in linear time

Question

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.

Answer 1

• $M\gets\emptyset$

• While $E\neq\emptyset$ do

  • select $(u,v)\in E$
  • $M \gets M \cup \{(u,v)\}$
  • delete all edges incident to $u$ and $v$

• Return $M$

The above algorithm runs in $O(m+n)$ time if we store $G=(V,E)$ using adjacency list.

Now we prove this algorithm is 2-approximation. Let OPT be the maximum matching. For each edge $e\in$ OPT, there must exist $e'\in M$ s.t. $|e\cap e'|\in\{1,2\}$, i.e. $e$ and $e'$ share one or two common vertex. Moreover, at most two different edges of OPT are incident to the same edge of $M$.

Now we divide OPT into two disjoint subsets OPT$_1$ and OPT$_2$. In OPT$_1$, no two edges are incident to the same edge in $M$. In other words, $M$ has a subset $M_1$ s.t. OPT$_1$ and $M_1$ are one-to-one, which implies $|OPT_1|=|M_1|$. We can pair all edges in OPT$_2$ s.t. different pairt of edges in $OPT_2$ are mapped to different edges in $M_2\subseteq M$. It's easy to show that $M_1\cap M_2=\emptyset$ and $M_1\cup M_2 = M$.

We have $|M|=|M_1|+|M_2|$ and $|OPT|=|OPT_1|+|OPT_2|=|M_1|+2|M_2|$. Therefore, $2|M|\geq|OPT|$.

Edited on Jan. 15, 2020:

The following is a simpler argument. For every matching $M$, we have $2\#edges(M)=\#vertices(M)$. For each $e=(u,v)$ in the maximum matching $M^*$, at least one of $u$ and $v$ appears in a maximal matching $M$. Otherwise, $M$ isn't maximal. Hence, $2\#edges(M)=\#vertices(M)\geq\#edges(M^*)$.

Answer 2

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$
   3. 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^*|$.