Matching is as easy as matrix inversion | Combinatorica Skip to main content
Springer Nature Link
Log in

Matching is as easy as matrix inversion

  • Published:
Combinatorica Aims and scope Submit manuscript

Abstract

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

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. S. A. Cook, A Taxonomy of Problems with Fast Parallel Algorithms,Information and Control,64 (1985), 2–22.

    Article  MATH  MathSciNet  Google Scholar 

  2. L. Csánky, Fast Parallel Matrix Inversion Algorithms.SIAM J. Computing,5 (1976), 618–623.

    Article  MATH  Google Scholar 

  3. J. Edmonds, Paths, Trees and Flowers,Canad. J. Math.,17 (1965), 449–467.

    MATH  MathSciNet  Google Scholar 

  4. J. Edmonds, Systems of Distinct Representatives and Linear Algebra,J. Res. Nat. Bureau of Standards, 71B,4 (1967), 241–245.

    MathSciNet  Google Scholar 

  5. Z. Galil andV. Pan, Improved Processor Bounds for Algebraic and Combinatorial Problems in RNC,Twenty Sixth Annual IEEE Symp. on the Foundations of Computer Science. (1985), 490–495.

  6. H. Karloff, A Randomized Parallel Algorithm for the Odd Set Cover Problem,Combinatorica 6 (1986), 387–391.

    MATH  MathSciNet  Google Scholar 

  7. R. M. Karp, E. Upfal andA. Wigderson, Finding a Maximum Matching is in Random NC,Seventeenth Annual Symp. on Theory of Computing. (1985), 22–32.

  8. R. M. Karp, E. Upfal andA. Wigderson, Are Search and Decision Problems Computationally Equivalent?Seventeenth Annual Symp. on Theory of Computing. (1985).

  9. D. Kozen, U. V. Vazirani andV. V. Vazirani, NC Algorithms for Comparability Graphs, Interval graphs, and Testing for Unique Perfect Matching,Fifth Annual Foundations of Software Technology and Theoretical Computer Science Conference (1985), invited paper inTheoretical Computer Science.

  10. L. Lovász, On Determinants, Matchings and Random Algorithms,Fundamentals of Computing Theory, edited by L. Budach, Akademia-Verlag, Berlin, (1979).

    Google Scholar 

  11. L. Lovász,Combinatorial Problems and Exercises, Akadémiai Kiadó, and North-Holland, Amsterdam, (1979).

    MATH  Google Scholar 

  12. L. Lovász andM. Plummer,Matcing Theory, Academic Press, Budapest, Hungary, (1986).

    Google Scholar 

  13. S. Micali andV. V. Vazirani, AnO(√|V||E|) Algorithm for Finding Maximum Matching in General Graphs,Twenty First Annual IEEE Symp. on the Foundations of Computer Science (1980), 17–27.

  14. V. Pan, Fast and Efficient Algorithms for the Exact Inversion of Integer Matrices,Fifth Annual Foundations of Software Technology and Theoretical Computer Science Conference (1985).

  15. C. H. Papadimitriou andM. Yannakakis, The Complexity of Restricted Spanning Tree Problems,Journal of the ACM,29 (1982), 285–309.

    Article  MATH  MathSciNet  Google Scholar 

  16. M. O. Rabin andV. V. Vazirani, Maximum Matching in General Gaphs Through Randomization, submitted.

  17. J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities.J. of ACM,27 (1980), 701–717.

    Article  MATH  Google Scholar 

  18. W. T. Tutte, The Factorization of Linear Graphs,J. London Math. Soc.,22 (1947), 107–111.

    Article  MATH  MathSciNet  Google Scholar 

  19. L. G. Valiant andV. V. Vazirani, NP is as Easy as Detecting Unique Solutions,Seventeenth Annual Symp. on Theory of Computing. (1985), to appear inTheoretical Computer Science.

  20. U. V. Vazirani andV. V. Vazirani, The Two-Processor Scheduling Problem is in Random NC,Seventeenth Annual Symp. on Theory of Computing (1985), 11–21, submitted.

  21. A. Borodin, S. A. Cook andN. Pippinger, Parallel Computation for Well-endowed Rings and Space Bounded ProbabilisticMachines, Information and Control,58 (1983) 113–136.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Comp. Sci. Dept., University of California, 94720, Berkeley, CA, USA

    Ketan Mulmuley (Miller Fellow)

  2. MSRI, 94720, Berkeley, CA, USA

    Umesh V. Vazirani

  3. Comp. Sci. Dept., Cornell University, 14853, Ithaca, NY, USA

    Vijay V. Vazirani

Authors
  1. Ketan Mulmuley
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Umesh V. Vazirani
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Vijay V. Vazirani
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

Work done while visiting MSRI, Berkeley, in Fall 1985.

Supported by NSF Grant BCR 85-03611 and an IBM Faculty Development Award.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Mulmuley, K., Vazirani, U.V. & Vazirani, V.V. Matching is as easy as matrix inversion. Combinatorica 7, 105–113 (1987). https://doi.org/10.1007/BF02579206

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02579206

AMS subject classification (1980)

Search

Navigation