{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,2]],"date-time":"2022-04-02T22:22:33Z","timestamp":1648938153914},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"name":"NSF","award":["CCF-1815901"]},{"name":"DIMACS\/Simons Collaboration on Bridging Continuous and Discrete Optimization","award":["CCF-1740425"]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,8,13]]},"abstract":"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 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","source":"Crossref","is-referenced-by-count":2,"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"}]},{"given":"Vijay V.","family":"Vazirani","sequence":"additional","affiliation":[{"name":"University of California, Irvine, California"}]}],"member":"320","reference":[{"key":"e_1_2_1_1_1","volume-title":"Innovations in Theoretical Computer Science","author":"Anari Nima","year":"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","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","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"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 31st ACM Symposium on Parallelism in Algorithms and Architectures.","author":"Eppstein David"},{"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","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","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_2_1_14_1","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.5555\/11534.11537"},{"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","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","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","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"},{"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","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"},{"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\/pdf\/10.1145\/3397504","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,3]],"date-time":"2021-03-03T12:46:29Z","timestamp":1614775589000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3397504"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,13]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,13]]}},"alternative-id":["10.1145\/3397504"],"URL":"http:\/\/dx.doi.org\/10.1145\/3397504","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":["Artificial Intelligence","Hardware and Architecture","Information Systems","Control and Systems Engineering","Software"],"published":{"date-parts":[[2020,8,13]]}}}