License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.54
URN: urn:nbn:de:0030-drops-117399
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11739/
Anari, Nima ;
Vazirani, Vijay V.
Matching Is as Easy as the Decision Problem, in the NC Model
Abstract
Is matching in NC, i.e., is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in TCS for over three decades, ever since the discovery of randomized NC matching algorithms [Karp et al., 1985; Mulmuley et al., 1987]. Over the last five years, the theoretical computer science community has launched a relentless attack on this question, leading to the discovery of several powerful ideas. We give what appears to be the culmination of this line of work: An NC algorithm for finding a minimum-weight perfect matching in a general graph with polynomially bounded edge weights, provided it is given an oracle for the decision problem. Consequently, for settling the main open problem, it suffices to obtain an NC algorithm for the decision problem. We believe this new fact has qualitatively changed the nature of this open problem.
All known efficient matching algorithms for general graphs follow one of two approaches: given by [Edmonds, 1965] and [Lovász, 1979]. Our oracle-based algorithm follows a new approach and uses many of ideas discovered in the last five years.
The difficulty of obtaining an NC perfect matching algorithm led researchers to study matching vis-a-vis clever relaxations of the class NC. In this vein, recently [Goldwasser and Grossman, 2015] gave a pseudo-deterministic RNC algorithm for finding a perfect matching in a bipartite graph, i.e., an RNC algorithm with the additional requirement that on the same graph, it should return the same (i.e., unique) perfect matching for almost all choices of random bits. A corollary of our reduction is an analogous algorithm for general graphs.
BibTeX - Entry
@InProceedings{anari_et_al:LIPIcs:2020:11739,
author = {Nima Anari and Vijay V. Vazirani},
title = {{Matching Is as Easy as the Decision Problem, in the NC Model}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {54:1--54:25},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11739},
URN = {urn:nbn:de:0030-drops-117399},
doi = {10.4230/LIPIcs.ITCS.2020.54},
annote = {Keywords: Parallel Algorithm, Pseudo-Deterministic, Perfect Matching, Tutte Matrix}
}
|
Keywords: |
|
Parallel Algorithm, Pseudo-Deterministic, Perfect Matching, Tutte Matrix |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
