Fast Distributed Approximation Algorithm for the Maximum Matching Problem in Bounded Arboricity Graphs

摘要

We give a deterministic distributed approximation algorithm for the maximum matching problem in graphs of bounded arboricity. Specifically, given 0 < ∈ < 1 and a positive integer a, the algorithm finds a matching of size at least (1 - ∈)m(G), where m(G) is the size of the maximum matching in an n-vertex graph G with arboricity at most a. The algorithm runs in O(log~* n) rounds in the message passing model and it is the first sublogarithmic algorithm for the problem on such a wide class of graphs. Moreover, the result implies that the known Ω((log n/log log n)~(1/2)) lower bound on the time complexity for a constant or polylogarithmic approximation does not hold for graphs of bounded arboricity.