2021-12-06T03:34:21Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:002122402021-08-17T15:00:00Z01164:02592:10486:10653
A Subquadratic-Time Distributed Algorithm for Exact Maximum MatchingA Subquadratic-Time Distributed Algorithm for Exact Maximum Matchingenghttp://id.nii.ac.jp/1001/00212134/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=212240&item_no=1&attribute_id=1&file_no=1Copyright (c) 2021 by the Information Processing Society of JapanNagoya Institute of TechnologyOsaka UniversityNaoki, KitamuraTaisuke, IzumiFor a graph G = (V, E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms has not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized O(s3/2max + log n)-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.For a graph G = (V, E), finding a set of disjoint edges that do not share any vertices is called a matching problem, and finding the maximum matching is a fundamental problem in the theory of distributed graph algorithms. Although local algorithms for the approximate maximum matching problem have been widely studied, exact algorithms has not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of O(n2) rounds is known for general instances. In this paper, we propose a randomized O(s3/2max + log n)-round algorithm in the CONGEST model, where smax is the size of maximum matching. This is the first exact maximum matching algorithm in o(n2) rounds for general instances in the CONGEST model. The key technical ingredient of our result is a distributed algorithms of finding an augmenting path in O(smax) rounds, which is based on a novel technique of constructing a sparse certificate of augmenting paths, which is a subgraph of the input graph preserving at least one augmenting path. To establish a highly parallel construction of sparse certificates, we also propose a new characterization of sparse certificates, which might also be of independent interest.AN1009593X研究報告アルゴリズム（AL）2021-AL-1841182021-08-182188-85662021-08-11