Problem

Maximal matching

A matching in a graph $G = (V, E)$ is a set $M \subseteq E$ of edges, no two of which share an endpoint. A matching is maximal if no edge can be added to it, that is, every edge of $G$ shares an endpoint with some edge of $M$.

A maximal matching of $G$ is exactly a maximal independent set of the line graph $L(G)$, and it is a $2$-approximation of both maximum matching and minimum vertex cover.

Runtimes are given in rounds, in terms of the number of nodes $n$ and the maximum degree $\Delta$.

A maximal matching A graph with eleven nodes. Four highlighted edges form a maximal matching; the three unmatched nodes have only matched neighbors.
matching edges unmatched nodes Every unmatched node has only matched neighbors, so no edge can be added. The matching is maximal but not maximum: this graph has a matching with five edges.