# Find a maximum matching in linear time

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.

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

## 2 Answers

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

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