[日時] 2023年12月21日(木) 12:20--13:20
[場所] 東京大学 本郷キャンパス 工14号館 534室
[講演者] 山口 勇太郎 (大阪大学)
[題目(title)] A Nearly Linear-Time Distributed Algorithm for Exact Maximum Matching
[概要(Abstract)]
We propose a randomized O(s log s)-round algorithm for finding a maximum-cardinality matching in general graphs under the CONGEST model, which is a standard distributed computational model, where s denotes the maximum size of a matching.The main contribution is proposing an algorithm to find an augmenting path of length l within O(l) rounds. The algorithm is built on the top of several recent results: verification of a maximum matching (Ahmadi--Kuhn 2020) and construction of a sparse subgraph preserving the reachability with alternating paths (Kitamura--Izumi 2022). In particular, the latter (also using the former) lead to an O(s^1.5)-round CONGEST algorithm for the same problem. The last key to reduce it to nearly linear time is exploiting nice structural properties of shortest alternating paths.This is a joint work with Taisuke Izumi and Naoki Kitamura, which will appear in SODA 2024.