{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:42Z","timestamp":1750220442403,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T00:00:00Z","timestamp":1590796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1815901"],"award-info":[{"award-number":["CCF-1815901"]}]},{"name":"DIMACS\/Simons Collaboration on Bridging Continuous and Discrete Optimization","award":["CCF-1740425"],"award-info":[{"award-number":["CCF-1740425"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>Is perfect matching in NC? That is, is there a deterministic fast parallel algorithm for it? This has been an outstanding open question in theoretical computer science for over three decades, ever since the discovery of RNC perfect matching algorithms. Within this question, the case of planar graphs has remained an enigma: On the one hand, counting the number of perfect matchings is far harder than finding one (the former is #P-complete and the latter is in P), and on the other, for planar graphs, counting has long been known to be in NC whereas finding one has resisted a solution.<\/jats:p>\n          <jats:p>In this article, we give an NC algorithm for finding a perfect matching in a planar graph. Our algorithm uses the above-stated fact about counting perfect matchings in a crucial way. Our main new idea is an NC algorithm for finding a face of the perfect matching polytope at which a set (which could be polynomially large) of conditions, involving constraints of the polytope, are simultaneously satisfied. Several other ideas are also needed, such as finding, in NC, a point in the interior of the minimum-weight face of this polytope and finding a balanced tight odd set.<\/jats:p>","DOI":"10.1145\/3397504","type":"journal-article","created":{"date-parts":[[2020,5,31]],"date-time":"2020-05-31T04:09:40Z","timestamp":1590898180000},"page":"1-34","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Planar Graph Perfect Matching Is in NC"],"prefix":"10.1145","volume":"67","author":[{"given":"Nima","family":"Anari","sequence":"first","affiliation":[{"name":"Stanford University, Stanford, California"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vijay V.","family":"Vazirani","sequence":"additional","affiliation":[{"name":"University of California, Irvine, California"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,5,30]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Vazirani","author":"Anari Nima","year":"2020","unstructured":"Nima Anari and Vijay V . Vazirani . 2020 . Matching is as easy as the decision problem, in the NC model. In Innovations in Theoretical Computer Science , 2020. Nima Anari and Vijay V. Vazirani. 2020. Matching is as easy as the decision problem, in the NC model. In Innovations in Theoretical Computer Science, 2020."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80060-6"},{"key":"e_1_2_1_3_1","volume-title":"All-pairs minimum cuts in near-linear time for surface-embedded graphs. Arxiv Preprint Arxiv:1411.7055","author":"Borradaile Glencora","year":"2014","unstructured":"Glencora Borradaile , David Eppstein , Amir Nayyeri , and Christian Wulff-Nilsen . 2014. All-pairs minimum cuts in near-linear time for surface-embedded graphs. Arxiv Preprint Arxiv:1411.7055 ( 2014 ). Glencora Borradaile, David Eppstein, Amir Nayyeri, and Christian Wulff-Nilsen. 2014. All-pairs minimum cuts in near-linear time for surface-embedded graphs. Arxiv Preprint Arxiv:1411.7055 (2014)."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"e_1_2_1_5_1","volume-title":"Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B 69B","author":"Edmonds J.","year":"1965","unstructured":"J. Edmonds . 1965. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B 69B ( 1965 ), 125--130. J. Edmonds. 1965. Maximum matching and a polyhedron with 0,1-vertices. Journal of Research of the National Bureau of Standards B 69B (1965), 125--130."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1965-045-4"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591865"},{"volume-title":"Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures.","author":"Eppstein David","key":"e_1_2_1_8_1","unstructured":"David Eppstein and Vijay V. Vazirani . 2019. 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 31st ACM Symposium on Parallelism in Algorithms and Architectures. David Eppstein and Vijay V. Vazirani. 2019. 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 31st ACM Symposium on Parallelism in Algorithms and Architectures."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973082.88"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897564"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.37236\/1438"},{"key":"e_1_2_1_12_1","first-page":"208","article-title":"Perfect bipartite matching in pseudo-deterministic RNC","volume":"22","author":"Goldwasser Shafi","year":"2015","unstructured":"Shafi Goldwasser and Ofer Grossman . 2015 . Perfect bipartite matching in pseudo-deterministic RNC . In Electronic Colloquium on Computational Complexity (ECCC) , Vol. 22. 208 . Shafi Goldwasser and Ofer Grossman. 2015. Perfect bipartite matching in pseudo-deterministic RNC. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 22. 208.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_13_1","first-page":"182","article-title":"Linear matroid intersection is in quasi-NC","volume":"23","author":"Gurjar Rohit","year":"2016","unstructured":"Rohit Gurjar and Thomas Thierauf . 2016 . Linear matroid intersection is in quasi-NC . In Electronic Colloquium on Computational Complexity (ECCC) , Vol. 23. 182 . Rohit Gurjar and Thomas Thierauf. 2016. Linear matroid intersection is in quasi-NC. In Electronic Colloquium on Computational Complexity (ECCC), Vol. 23. 182.","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_14_1","volume-title":"Vishnoi","author":"Gurjar Rohit","year":"2017","unstructured":"Rohit Gurjar , Thomas Thierauf , and Nisheeth K . Vishnoi . 2017 . Isolating a vertex via lattices: Polytopes with totally unimodular faces. Arxiv Preprint Arxiv :1708.02222 (2017). Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi. 2017. Isolating a vertex via lattices: Polytopes with totally unimodular faces. Arxiv Preprint Arxiv:1708.02222 (2017)."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/31846.31849"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8191(85)90026-2"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579407"},{"key":"e_1_2_1_19_1","volume-title":"Graph theory and crystal physics. Graph Theory and Theoretical Physics","author":"Kasteleyn Pieter","year":"1967","unstructured":"Pieter Kasteleyn . 1967. Graph theory and crystal physics. Graph Theory and Theoretical Physics ( 1967 ), 43--110. Pieter Kasteleyn. 1967. Graph theory and crystal physics. Graph Theory and Theoretical Physics (1967), 43--110."},{"key":"e_1_2_1_20_1","first-page":"2008","article-title":"Some perfect matchings and perfect half-integral matchings in NC","volume":"4","author":"Kulkarni Raghav","year":"2008","unstructured":"Raghav Kulkarni , Meena Mahajan , and Kasturi R, Varadarajan. 2008 . Some perfect matchings and perfect half-integral matchings in NC . Chicago Journal of Theoretical Computer Science 4 , 2008 . Raghav Kulkarni, Meena Mahajan, and Kasturi R, Varadarajan. 2008. Some perfect matchings and perfect half-integral matchings in NC. Chicago Journal of Theoretical Computer Science 4, 2008.","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"e_1_2_1_21_1","first-page":"565","article-title":"On determinants, matchings, and random algorithms","volume":"79","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1979","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz . 1979 . On determinants, matchings, and random algorithms . In FCT , Vol. 79. 565 -- 574 . L\u00e1szl\u00f3 Lov\u00e1sz. 1979. On determinants, matchings, and random algorithms. In FCT, Vol. 79. 565--574.","journal-title":"FCT"},{"key":"e_1_2_1_22_1","unstructured":"L. Lov\u00e1sz and M. D. Plummer. 1986. Matching Theory. North-Holland Amsterdam\u2013New York.  L. Lov\u00e1sz and M. D. Plummer. 1986. Matching Theory. North-Holland Amsterdam\u2013New York."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215074"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335346"},{"key":"e_1_2_1_25_1","volume-title":"Proceedings of the 30th Annual Symposium on Foundations of Computer Science","author":"Gary","year":"1989","unstructured":"Gary L. Miller and Joseph Naor. 1989. Flow in planar graphs with multiple sources and sinks . In Proceedings of the 30th Annual Symposium on Foundations of Computer Science , 1989 . IEEE, 112--117. Gary L. Miller and Joseph Naor. 1989. Flow in planar graphs with multiple sources and sinks. In Proceedings of the 30th Annual Symposium on Foundations of Computer Science, 1989. IEEE, 112--117."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.7.1.67"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/322307.322309"},{"key":"e_1_2_1_29_1","volume-title":"On the structure of all minimum cuts in a network and applications. Combinatorial Optimization II","author":"Picard Jean-Claude","year":"1980","unstructured":"Jean-Claude Picard and Maurice Queyranne . 1980. On the structure of all minimum cuts in a network and applications. Combinatorial Optimization II ( 1980 ), 8--16. Jean-Claude Picard and Maurice Queyranne. 1980. On the structure of all minimum cuts in a network and applications. Combinatorial Optimization II (1980), 8--16."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Sankowski Piotr","year":"2018","unstructured":"Piotr Sankowski . 2018 . NC algorithms for weighted planar perfect matching and related problems . In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Piotr Sankowski. 2018. NC algorithms for weighted planar perfect matching and related problems. In Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.70"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214061"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90017-5"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397504","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3397504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:33Z","timestamp":1750193253000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,30]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3397504"],"URL":"https:\/\/doi.org\/10.1145\/3397504","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2020,5,30]]},"assertion":[{"value":"2018-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}