Matching is as easy as matrix inversion
type: Item
instance of: scholarly article
title: Matching is as easy as matrix inversion
zbMATH Open document ID: 0632.68041
DOI: 10.1007/BF02579206
author: Umesh V. Vazirani
author: Vijay V. Vazirani
author: Ketan D. Mulmuley
published in: Combinatorica
publication date: 1987-01-01T00:00:00Z
review text: This paper presents a randomized parallel algorithm which finds a maximum matching in an n-vertex m-edge graph in \(O(\log^ 2 n)\) time using \(O(n^{3.5} m)\) processors. This result improves upon the \(RNC^ 2\) algorithm of \textit{L. Lovasz} [Fundamentals of computation theory '79, Proc. Conf., Berlin/Wendisch-Rietz 1979, 565-574 (1979; Zbl 0446.68036)] for deciding if a graph has a perfect matching, and the \(RNC^ 3\) algorithm of \textit{R. M. Karp}, \textit{E. Uppal} and \textit{A. Wigderson} [Finding a maximum matching is in random NC, Seventeenth Annual Symp. on Theory of Computing (1985)]. Other results presented include \(RNC^ 2\) algorithms for vertex-weighted matching and exact matching (a perfect matching which uses exactly k edges from a given edge-subset - a problem for which no deterministic polynomial algorithm is known), and a simpler proof of a theorem first proved by \textit{L. G. Valiant} and \textit{V. V. Vazrani} [Theor. Comput. Sci. 47, 85-95 (1986; Zbl 0621.68030)]. These results follow from Tutte's theorem relating the existence of a perfect matching to the invertibility of a certain \(n\times n\) matrix [\textit{W. T. Tutte}, J. Lond. Math. Soc. 22, 107-111 (1947; Zbl 0029.23301)], Pan's \(RNC^ 2\) matrix-inversion algorithm [\textit{V. Pan}, Lect. Notes Comput. Sci. 206, 504-521 (1985; Zbl 0598.68042)] and the ``isolating lemma'' introduced in the present paper: if S is a set of n elements, each of which is assigned an integer weight at random from [1,2n], and F is a family of subsets of S, then the probability that F has a unique minimum-weight set is at least 0.5.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C50
zbMATH DE Number: 4028897
zbMATH Keywords: matrix inversion
zbMATH Keywords: probabilistic methods
zbMATH Keywords: randomized parallel algorithm
zbMATH Keywords: maximum matching
Wikidata QID: Q30053548
reviewed by: Timothy R. S. Walsh
MaRDI profile type: Publication
cites work: A taxonomy of problems with fast parallel algorithms
cites work: Fast Parallel Matrix Inversion Algorithms
cites work: Paths, Trees, and Flowers
cites work: Systems of distinct representatives and linear algebra
cites work: A Las Vegas RNC algorithm for maximum matching
cites work: Q3732972
cites work: The complexity of restricted spanning tree problems
cites work: Maximum matchings in general graphs through randomization
cites work: Fast Probabilistic Algorithms for Verification of Polynomial Identities
cites work: The Factorization of Linear Graphs
cites work: NP is as easy as detecting unique solutions
cites work: The Two-Processor Scheduling Problem is in Random NC
cites work: Parallel computation for well-endowed rings and space-bounded probabilistic machines
DBLP publication ID: journals/combinatorica/MulmuleyVV87
description: scientific article; zbMATH DE number 4028897