The search functionality is under construction.

The search functionality is under construction.

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 have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of *O*(*n*^{2}) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where *s*_{max} is the size of maximum matching. This is the first exact maximum matching algorithm in *o*(*n*^{2}) 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*(*s*_{max}) 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.

- Publication
- IEICE TRANSACTIONS on Information Vol.E105-D No.3 pp.634-645

- Publication Date
- 2022/03/01

- Publicized
- 2021/12/17

- Online ISSN
- 1745-1361

- DOI
- 10.1587/transinf.2021EDP7083

- Type of Manuscript
- PAPER

- Category
- Software System

Naoki KITAMURA

Nagoya Institute of Technology

Taisuke IZUMI

Osaka University

The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.

Copy

Naoki KITAMURA, Taisuke IZUMI, "A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching" in IEICE TRANSACTIONS on Information,
vol. E105-D, no. 3, pp. 634-645, March 2022, doi: 10.1587/transinf.2021EDP7083.

Abstract: 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 have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of *O*(*n*^{2}) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where *s*_{max} is the size of maximum matching. This is the first exact maximum matching algorithm in *o*(*n*^{2}) 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*(*s*_{max}) 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.

URL: https://global.ieice.org/en_transactions/information/10.1587/transinf.2021EDP7083/_p

Copy

@ARTICLE{e105-d_3_634,

author={Naoki KITAMURA, Taisuke IZUMI, },

journal={IEICE TRANSACTIONS on Information},

title={A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching},

year={2022},

volume={E105-D},

number={3},

pages={634-645},

abstract={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 have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of *O*(*n*^{2}) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where *s*_{max} is the size of maximum matching. This is the first exact maximum matching algorithm in *o*(*n*^{2}) 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*(*s*_{max}) 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.},

keywords={},

doi={10.1587/transinf.2021EDP7083},

ISSN={1745-1361},

month={March},}

Copy

TY - JOUR

TI - A Subquadratic-Time Distributed Algorithm for Exact Maximum Matching

T2 - IEICE TRANSACTIONS on Information

SP - 634

EP - 645

AU - Naoki KITAMURA

AU - Taisuke IZUMI

PY - 2022

DO - 10.1587/transinf.2021EDP7083

JO - IEICE TRANSACTIONS on Information

SN - 1745-1361

VL - E105-D

IS - 3

JA - IEICE TRANSACTIONS on Information

Y1 - March 2022

AB - 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 have not been much studied. In fact, no exact maximum matching algorithm that is faster than the trivial upper bound of *O*(*n*^{2}) rounds is known for general instances. In this paper, we propose a randomized $O(s_{max}^{3/2})$-round algorithm in the CONGEST model, where *s*_{max} is the size of maximum matching. This is the first exact maximum matching algorithm in *o*(*n*^{2}) 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*(*s*_{max}) 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.

ER -