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 < epsilon < 1 and a positive integer a, the algorithm finds a matching of size at least (1 - epsilon)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 Omega(root log n/ log log n) lower bound on the time complexity for a constant or polylogarithmic approximation does not hold for graphs of bounded arboricity.