Document Open Access Logo

Matching Is as Easy as the Decision Problem, in the NC Model

Authors Nima Anari, Vijay V. Vazirani

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.54.pdf
  • Filesize: 0.57 MB
  • 25 pages

Document Identifiers

Author Details

Nima Anari
  • Computer Science Department, Stanford University, CA, United States
Vijay V. Vazirani
  • Computer Science Department, University of California, Irvine, CA, United States

Funding

  • Vazirani, Vijay V.: Supported in part by NSF grant CCF-1815901.

Cite AsGet BibTex

Nima Anari and Vijay V. Vazirani. Matching Is as Easy as the Decision Problem, in the NC Model. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 54:1-54:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.54

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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parallel algorithms
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Pseudorandomness and derandomization
Keywords
  • Parallel Algorithm
  • Pseudo-Deterministic
  • Perfect Matching
  • Tutte Matrix

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Nima Anari and Vijay V. Vazirani. Planar Graph Perfect Matching is in NC. In Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 2018. Google Scholar
  2. Alberto Caprara, Alessandro Panconesi, and Romeo Rizzi. Packing cycles in undirected graphs. Journal of Algorithms, 48(1):239-256, 2003. Google Scholar
  3. Laszlo Csanky. Fast parallel matrix inversion algorithms. SIAM Journal on Computing, 5(4):618-623, 1976. Google Scholar
  4. Marek Cygan, Harold N Gabow, and Piotr Sankowski. Algorithmic Applications of Baur-Strassen’s Theorem: Shortest Cycles, Diameter and Matchings. arXiv preprint, 2012. URL: http://arxiv.org/abs/1204.1616.
  5. Samir Datta, Raghav Kulkarni, and Sambuddha Roy. Deterministically isolating a perfect matching in bipartite planar graphs. Theory of Computing Systems, 47(3):737-757, 2010. Google Scholar
  6. Jack Edmonds. Maximum matching and a polyhedron with 0, 1-vertices. Journal of research of the National Bureau of Standards B, 69(125-130):55-56, 1965. Google Scholar
  7. David Eppstein and Vijay V. Vazirani. NC Algorithms for Computing a Perfect Matching, Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs. In Proceedings of the Thirty-First ACM Symposium on Parallelism in Algorithms and Architectures, 2019. Google Scholar
  8. Stephen Fenner, Rohit Gurjar, and Thomas Thierauf. Bipartite perfect matching is in quasi-NC. In Proceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 754-763. ACM, 2016. Google Scholar
  9. Eran Gat and Shafi Goldwasser. Probabilistic Search Algorithms with Unique Answers and Their Cryptographic Applications. In Electronic Colloquium on Computational Complexity (ECCC), volume 18, page 136, 2011. Google Scholar
  10. Shafi Goldwasser and Ofer Grossman. Perfect Bipartite Matching in Pseudo-Deterministic RNC. In Electronic Colloquium on Computational Complexity (ECCC), volume 22, page 208, 2015. Google Scholar
  11. Rohit Gurjar and Thomas Thierauf. Linear matroid intersection is in quasi-NC. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 821-830. ACM, 2017. Google Scholar
  12. Rohit Gurjar, Thomas Thierauf, and Nisheeth K Vishnoi. Isolating a vertex via lattices: Polytopes with totally unimodular faces. arXiv preprint, 2017. URL: http://arxiv.org/abs/1708.02222.
  13. John E Hopcroft and Richard M Karp. An n^5/2 algorithm for maximum matchings in bipartite graphs. SIAM Journal on computing, 2(4):225-231, 1973. Google Scholar
  14. Mark Jerrum, Alistair Sinclair, and Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. Journal of the ACM (JACM), 51(4):671-697, 2004. Google Scholar
  15. Mark R Jerrum, Leslie G Valiant, and Vijay V Vazirani. Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science, 43:169-188, 1986. Google Scholar
  16. Donald B Johnson. Parallel algorithms for minimum cuts and maximum flows in planar networks. Journal of the ACM (JACM), 34(4):950-967, 1987. Google Scholar
  17. Richard M Karp, Eli Upfal, and Avi Wigderson. Are search and decision programs computationally equivalent? In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 464-475. ACM, 1985. Google Scholar
  18. Richard M Karp, Eli Upfal, and Avi Wigderson. Constructing a perfect matching is in random NC. Combinatorica, 6(1):35-48, 1986. Google Scholar
  19. Alexander V Karzanov. O nakhozhdenii maksimal'nogo potoka v setyakh spetsial'nogo vida i nekotorykh prilozheniyakh; title translation: On finding maximum flows in networks with special structure and some applications. Mathematicheskie Voprosy Upravleniya Proizvodstvom, 1973. Google Scholar
  20. László Lovász. On determinants, matchings, and random algorithms. In FCT, volume 79, pages 565-574, 1979. Google Scholar
  21. László Lovász and Michael D Plummer. Matching theory, volume 367. American Mathematical Soc., 2009. Google Scholar
  22. Michael Luby. A simple parallel algorithm for the maximal independent set problem. SIAM journal on computing, 15(4):1036-1053, 1986. Google Scholar
  23. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Foundations of Computer Science (FOCS), 2013 IEEE 54th Annual Symposium on, pages 253-262. IEEE, 2013. Google Scholar
  24. Meena Mahajan and Kasturi R Varadarajan. A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 351-357. ACM, 2000. Google Scholar
  25. Silvio Micali and Vijay V Vazirani. An O(√|V| |E|) algorithm for finding maximum matching in general graphs. In Foundations of Computer Science, 1980., 21st Annual Symposium on, pages 17-27, 1980. Google Scholar
  26. Gary L Miller and Joseph Naor. Flow in planar graphs with multiple sources and sinks. In Foundations of Computer Science, 1989., 30th Annual Symposium on, pages 112-117. IEEE, 1989. Google Scholar
  27. Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani. Matching is as easy as matrix inversion. In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 345-354. ACM, 1987. Google Scholar
  28. Manfred W Padberg and M Ram Rao. Odd minimum cut-sets and b-matchings. Mathematics of Operations Research, 7(1):67-80, 1982. Google Scholar
  29. Christos H Papadimitriou and Mihalis Yannakakis. The complexity of restricted spanning tree problems. Journal of the ACM (JACM), 29(2):285-309, 1982. Google Scholar
  30. Michael O Rabin and Vijay V Vazirani. Maximum matchings in general graphs through randomization. Journal of Algorithms, 10(4):557-567, 1989. Google Scholar
  31. Piotr Sankowski. NC Algorithms for Weighted Planar Perfect Matching and Related Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  32. Ola Svensson and Jakub Tarnawski. The matching problem in general graphs is in quasi-NC. In Foundations of Computer Science (FOCS), 2017 IEEE 58th Annual Symposium on, pages 696-707, 2017. Google Scholar
  33. Leslie G Valiant. The complexity of computing the permanent. Theoretical computer science, 8(2):189-201, 1979. Google Scholar
  34. Vijay V Vazirani. NC algorithms for computing the number of perfect matchings in K3, 3-free graphs and related problems. Information and computation, 80(2):152-164, 1989. Google Scholar
  35. Vijay V Vazirani. A theory of alternating paths and blossoms for proving correctness of the O(√|V| |E|) general graph maximum matching algorithm. Combinatorica, 14(1):71-109, 1994. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact