We initiate the study of approximate maximum matching in the vertex partition
model, for graphs subject to dynamic changes. We assume that the $n$ vertices
of the graph are partitioned among $k$ players, who execute a distributed
algorithm and communicate via message passing. An adaptive adversary may
perform dynamic updates to the graph topology by inserting or removing edges
between the nodes, and the algorithm needs to respond to these changes by
adapting the output of the players, with the goal of maintaining an approximate
maximum matching. The main performance metric in this setting is the
algorithm’s update time, which corresponds to the number of rounds required for
updating the solution upon an adversarial change. For the standard setting of
single-edge insertions and deletions, we obtain the following results:
We give a randomized Las Vegas algorithm with an expected update time of $O(
\frac{\sqrt{m}}{\beta k} )$ rounds that maintains a $\frac{2}{3}$-approximate
maximum matching that is also maximal, where $m$ is the number of edges of the
graph. We also show that any algorithm has a worst case update time of $\Omega(
\frac{n}{\beta k^2\log n} )$, assuming a link bandwidth of $O(\beta\log n)$
bits per round, if it maintains a matching that is maximal and does not have
any 3-augmenting paths. For batch-dynamic updates, where the adversary may
modify up to $\ell\ge 1$ edges at once, we prove the following: There is a
randomized algorithm that succeeds with high probability in maintaining a
$\frac{2}{3}$-approximate maximum matching and has a worst case update time of
$\Omega( \frac{\ell\log n}{\sqrt{\beta k}} )$ rounds. We show that $\Omega(
\frac{\ell}{\beta k \log n} )$ poses a lower bound for maintaining a maximal
matching without 3-augmenting paths.

Cet article explore les excursions dans le temps et leurs implications.

Télécharger PDF: