TY - GEN
T1 - Dynamic Maximal Matching in Clique Networks
AU - Li, Minming
AU - Robinson, Peter
AU - Zhu, Xianbin
N1 - Publisher Copyright:
© 2024 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.
PY - 2024/1
Y1 - 2024/1
N2 - We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n nodes is vertex-partitioned among k players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of edge insertions or deletions. We first show a lower bound of ω log k k2 log n rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of ω( k log n ) rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of O n k log n rounds, while achieving an update time that that is independent of n: In more detail, the update time is O k log k against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes O k log k rounds.
AB - We consider the problem of computing a maximal matching with a distributed algorithm in the presence of batch-dynamic changes to the graph topology. We assume that a graph of n nodes is vertex-partitioned among k players that communicate via message passing. Our goal is to provide an efficient algorithm that quickly updates the matching even if an adversary determines batches of edge insertions or deletions. We first show a lower bound of ω log k k2 log n rounds for recomputing a matching assuming an oblivious adversary who is unaware of the initial (random) vertex partition as well as the current state of the players, and a stronger lower bound of ω( k log n ) rounds against an adaptive adversary, who may choose any balanced (but not necessarily random) vertex partition initially and who knows the current state of the players. We also present a randomized algorithm that has an initialization time of O n k log n rounds, while achieving an update time that that is independent of n: In more detail, the update time is O k log k against an oblivious adversary, who must fix all updates in advance. If we consider the stronger adaptive adversary, the update time becomes O k log k rounds.
KW - distributed graph algorithm
KW - dynamic network
KW - lower bound
KW - maximal matching
KW - randomized algorithm
UR - http://www.scopus.com/inward/record.url?scp=85184141994&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85184141994&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.ITCS.2024.73
DO - 10.4230/LIPIcs.ITCS.2024.73
M3 - Conference contribution
AN - SCOPUS:85184141994
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 15th Innovations in Theoretical Computer Science Conference, ITCS 2024
A2 - Guruswami, Venkatesan
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 15th Innovations in Theoretical Computer Science Conference, ITCS 2024
Y2 - 30 January 2024 through 2 February 2024
ER -