Suppose I have an undirected graph with four vertices $a,b,c,d$ which are connected as in a simple path from $a$ to $d$, i.e. the edge set $\{(a,b), (b,c), (c,d)\}$. Then I have seen the following proposed as a greedy algorithm to find a maximal matching here (page 2, middle of the page)

Maximal Matching (G, V, E):
M = []
While (no more edges can be added)
     Select an edge which does not have any vertex in common with edges in M
end while
return M

It seems that this algorithm is entirely dependent on the order chosen for which edge is chosen first. For instance in my example if you choose edge $(b,c)$ first, then the you will have a matching that consists only of $(b,c)$.

Whereas if you choose $(a,b)$ as your starting edge, then the next edge chosen will be $(c,d)$ and you have a matching of cardinality 2.

Am I missing something, as this seems wrong? I have also seen this described as an algorithm for finding a maximal matching in the context of proving that the vertex cover approximation algorithm selects a vertex cover by choosing edges according to a maximal matching. Any insights appreciated.


You're correct, you're not missing anything -- except that the algorithm is not wrong. The task is to choose a maximal matching, not a maximum matching. There may be many possible maximal matchings, many of which are not maximum matchings. It's the difference between a local optimum vs a global optimum.

| cite | improve this answer | |
  • $\begingroup$ @einpoklum-reinstateMonica, oh, so it is. Thanks. Edited. $\endgroup$ – D.W. Nov 5 '19 at 21:46

Your Answer

