2
$\begingroup$

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.

$\endgroup$
  • 2
    $\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
3
$\begingroup$
  • $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^*)$.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

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.