{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:32:31Z","timestamp":1750307551904,"version":"3.41.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,3,1]],"date-time":"2010-03-01T00:00:00Z","timestamp":1267401600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["CCF-0635084"],"award-info":[{"award-number":["CCF-0635084"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["428868","339262"],"award-info":[{"award-number":["428868","339262"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2010,3]]},"abstract":"<jats:p>\n            In this article we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first nontrivial algorithm, with running time\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            ), dates back to K\u00f6nig's work in 1916 (here\n            <jats:italic>m<\/jats:italic>\n            =\n            <jats:italic>nd<\/jats:italic>\n            is the number of edges in the graph, 2\n            <jats:italic>n<\/jats:italic>\n            is the number of vertices, and\n            <jats:italic>d<\/jats:italic>\n            is the degree of each node). The currently most efficient algorithm takes time\n            <jats:italic>O(m)<\/jats:italic>\n            , and is due to Cole et al. [2001]. We improve this running time to\n            <jats:italic>O<\/jats:italic>\n            (min{\n            <jats:italic>m<\/jats:italic>\n            ,\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2.5<\/jats:sup>\n            ln\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>d<\/jats:italic>\n            }); this minimum can never be larger than\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1.75<\/jats:sup>\n            \u221aln\n            <jats:italic>n<\/jats:italic>\n            ). We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a\n            <jats:italic>d<\/jats:italic>\n            -regular bipartite graph independently with a probability\n            <jats:italic>p<\/jats:italic>\n            =\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ln\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to nonexistence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Karger's sampling theorem [1994a, 1994b] for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            \u221a\n            <jats:italic>n<\/jats:italic>\n            ) algorithm (due to Hopcroft and Karp [1973]) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to polylogarithmic factors (in fact, up to ln\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/1721837.1721843","type":"journal-article","created":{"date-parts":[[2010,4,7]],"date-time":"2010-04-07T02:56:32Z","timestamp":1270608992000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Perfect matchings via uniform sampling in regular bipartite graphs"],"prefix":"10.1145","volume":"6","author":[{"given":"Ashish","family":"Goel","sequence":"first","affiliation":[{"name":"Stanford University, Palo Alto, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael","family":"Kapralov","sequence":"additional","affiliation":[{"name":"Stanford University, Palo Alto, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sanjeev","family":"Khanna","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,4,6]]},"reference":[{"volume-title":"Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03)","author":"Aggarwal G.","key":"e_1_2_1_1_1","unstructured":"Aggarwal , G. , Motwani , R. , Shah , D. , and Zhu , A . 2003. Switch scheduling via randomized edge coloring . In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03) . IEEE Computer Society, 502. Aggarwal, G., Motwani, R., Shah, D., and Zhu, A. 2003. Switch scheduling via randomized edge coloring. In Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science (FOCS'03). IEEE Computer Society, 502."},{"key":"e_1_2_1_3_1","first-page":"147","article-title":"Tres observaciones sobre el algebra lineal. Univ. Nac","volume":"5","author":"Birkhoff G.","year":"1946","unstructured":"Birkhoff , G. 1946 . Tres observaciones sobre el algebra lineal. Univ. Nac . Tucum\u00e1n Rev. Ser. A 5 , 147 -- 151 . Birkhoff, G. 1946. Tres observaciones sobre el algebra lineal. Univ. Nac. Tucum\u00e1n Rev. Ser. A 5, 147--151.","journal-title":"Tucum\u00e1n Rev. Ser. A"},{"volume-title":"Modern Graph Theory","author":"Bollob\u00e1s B.","key":"e_1_2_1_4_1","unstructured":"Bollob\u00e1s , B. 1998. Modern Graph Theory . Springer . Bollob\u00e1s, B. 1998. Modern Graph Theory. Springer."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211043"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/0211009"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195422"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94)","author":"Karger D. R.","year":"1994","unstructured":"Karger , D. R. 1994 b. Using randomized sparsification to approximate minimum cuts . In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94) . 424--432. Karger, D. R. 1994b. Using randomized sparsification to approximate minimum cuts. In Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'94). 424--432."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01456961"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.   Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.40"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796299266"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_17_1","first-page":"5","article-title":"A certain zero-sum two-person game equivalent to the optimal assignment problem","volume":"2","author":"von Neumann J.","year":"1953","unstructured":"von Neumann , J. 1953 . A certain zero-sum two-person game equivalent to the optimal assignment problem . Contrib. Optimal Assignm. Problem Theory Games 2 , 5 -- 12 . von Neumann, J. 1953. A certain zero-sum two-person game equivalent to the optimal assignment problem. Contrib. Optimal Assignm. Problem Theory Games 2, 5--12.","journal-title":"Contrib. Optimal Assignm. Problem Theory Games"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721843","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1721837.1721843","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T12:23:38Z","timestamp":1750249418000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1721837.1721843"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3]]},"references-count":16,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,3]]}},"alternative-id":["10.1145\/1721837.1721843"],"URL":"https:\/\/doi.org\/10.1145\/1721837.1721843","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2010,3]]},"assertion":[{"value":"2008-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-04-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}