Does the following 2-rounds distributed algorithm approximates a maximal matching well?

Question

Let $G$ be an undirected graph.

I'm looking for a two-rounds distributed algorithm that matches as many vertex pairs as possible.

Consider the following protocol for vertex $v$.

1. Use a fair coin to choose a ``status'' $s_v\in\{\mathit{active},\mathit{passive}\}$.

2.a. If $s_v=\mathit{active}$ send request to a random neighbor.

2.b. If $s_v=\mathit{passive}$ and you have received at least one request, respond with accept to a single requestor, chosen at random.

Each request paired with accept adds an edge to the resulting matching.

Let $M$ be a minimum maximal matching (i.e., the maximal matching with the smallest cardinality) of $G$, and let $M'$ be the matching generated by the above algorithm.

What can we say about $\mathbb E[|M'|] / |M|$? is the generated matching expected to be a good approximation for a maximal matching? e.g., do we have $\mathbb E[|M'|] / |M|=\Omega(1)$ for any graph $G$?

Answer 1

No. For the following graph the expected size of the generated matching is $O(\sqrt n)$, but any maximal matching has size $\Theta(n)$.

The graph consists of a $k$-vertex core $C$ and a matching $M_0$ of $k^2$ edges and vertices (disjoint from $C$), plus all edges $(u,w)$ where $u\in C$ and $w\in M_0$.

lemma 1. Any maximal matching $M$ has $\Omega(k^2)$ edges

Proof. Every edge in $M_0$ is either in $M$ or is touched by an edge in $M$ into $C$, but all at most $k$ edges of $M$ can touch $C$. QED

lemma 2. In your random process, the expected number of edges chosen in the random matching is $O(k)$.

Proof. Clearly at most $k$ edges are chosen that are not in $M_0$ (as there are only $k$ vertices in $C$). For a given edge $(u,w)$ in $M_0$, the chance that it is chosen is $O(1/k)$, because, given that, say, $u$ is active and $w$ is passive, the chance that $u$ picks $w$ is $O(1/k)$, as $w$ has $k$ other edges (to $C$). QED

(One thing you can prove about your process is that, for any graph, in expectation, a constant fraction of the edges will touch the edges in the generated matching. See e.g. here. Roughly, if you direct each edge $(u,w)$ from the lower-degree vertex to the higher-degree vertex, and call a vertex good if more than one-third of its incident edges are directed into it, then at least half the edges must be directed into good vertices (Lemma 6). And each good vertex has constant probability of being matched in your process. So, at least half the edges touch vertices that have a constant probability of being matched.

EDIT: So after $O(\log n)$ rounds of your process, it will have a maximal matching with high probability.)