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

<p>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$.</p>

<p><strong>lemma 1</strong>. <em>Any maximal matching $M$ has $\Omega(k^2)$ edges</em></p>

<p><em>Proof.</em> 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</p>

<p><strong>lemma 2</strong>. <em>In your random process, the expected number of edges chosen in the random matching is $O(k)$.</em></p>

<p><em>Proof.</em>  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</p>

<p>(One thing you can prove about your process is that, for any graph, in expectation, a constant fraction of the <em>edges</em> will touch the edges in the generated matching.  See e.g. <a href="https://arxiv.org/pdf/cs/0205037.pdf" rel="nofollow noreferrer">here</a>.  Roughly, if you direct each edge $(u,w)$ from the lower-degree vertex to the higher-degree vertex, and call a vertex <em>good</em> 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.</p>

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

CC BY-SA 3.0
2018-04-10T14:27:37.420Z
2018-04-10T15:42:52.497Z
2018-04-10T15:42:52.497Z
Neal Young
<p>Let $G$ be an undirected graph.</p>

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

<p>Consider the following protocol for vertex $v$.</p>

<ol>
<li>Use a fair coin to choose a ``status'' $s_v\in\{\mathit{active},\mathit{passive}\}$.</li>
</ol>

<p>2.a. If $s_v=\mathit{active}$ send <code>request</code> to a random neighbor. </p>

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

<p>Each <code>request</code> paired with <code>accept</code> adds an edge to the resulting matching.</p>

<p>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.</p>

<blockquote>
  <p>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$?</p>
</blockquote>

<ds.algorithms><approximation-algorithms><randomized-algorithms><dc.distributed-comp><matching>
Does the following 2-rounds distributed algorithm approximates a maximal matching well?
R B
# Does the following 2-rounds distributed algorithm approximates a maximal matching well?

(Asked by: username_0 on 2018-04-10)

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$?

**Tags:** ds.algorithms, approximation-algorithms, randomized-algorithms, dc.distributed-comp, matching

---

## 1 answers

### Answer by username_1 on 2018-04-10. Score: 1 | Accepted answer

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](https://arxiv.org/pdf/cs/0205037.pdf). 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.)


---

