Matching is as easy as matrix inversion

1987/01/01 by Ketan Mulmuley, Umesh Vazirani, Vijay V. Vazirani · 15 citations
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Optimization and Search Problems

paper · pdf · doi:10.1145/28395.383347

openalex publication_date 1987/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/31

Abstract

A new algorithm for finding a maximum matching in a general graph is presented; its special feature being that the only computationally non-trivial step required in its execution is the inversion of a single integer matrix. Since this step can be parallelized, we get a simple parallel (RNC2) algorithm. At the heart of our algorithm lies a probabilistic lemma, the isolating lemma. We show applications of this lemma to parallel computation and randomized reductions.

Citations

• The Factorization of Linear Graphs
• Paths, Trees, and Flowers

Cited by

• Lattice Problems, Gauge Functions and Parameterized Algorithms
• Detecting Feedback Vertex Sets of Size k in O^⋆(2.7^k) Time
• A Note on Polynomial Identity Testing for Depth-3 Circuits
• A fast quantum mechanical algorithm for database search
• Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds
• Optimization with More than One Budget
• Computational Complexity
• The Nature of Computation
• Complexity of induced subgraph isomorphism and maximum common induced subgraph parameterized by cluster vertex deletion number
• Parallel Algorithmic Techniques For CombinationalComputation
• Fast Parallel Algorithms for Reducible Flow Graphs
• A new rounding procedure for the assignment problem with applications to dense graph arrangement problems
• The matching problem for bipartite graphs with polynomially bounded permanents is in NC
• Primality and identity testing via Chinese remaindering
• Ketan Mulmuley [wikipedia]