{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T20:20:20Z","timestamp":1773433220583,"version":"3.50.1"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2018,3,13]],"date-time":"2018-03-13T00:00:00Z","timestamp":1520899200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["UMO-2012\/05\/D\/ST6\/03214"],"award-info":[{"award-number":["UMO-2012\/05\/D\/ST6\/03214"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council (ERC) under the European Union\u2019s Horizon 2020 research and innovation program","award":["677651"],"award-info":[{"award-number":["677651"]}]},{"name":"NWO grant \u201cSpace and Time Efficient Structural Improvements of Dynamic Programming Algorithms.\u201d"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2018,6,30]]},"abstract":"\n For an even integer\n t<\/jats:italic>\n \u2265 2, the Matching Connectivity matrix\n H<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n is a matrix that has rows and columns both labeled by all perfect matchings of the complete graph on\n t<\/jats:italic>\n vertices; an entry\n H<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n [\n M<\/jats:italic>\n 1<\/jats:sub>\n ,\n M<\/jats:italic>\n 2<\/jats:sub>\n ] is 1 if\n M<\/jats:italic>\n 1<\/jats:sub>\n and\n M<\/jats:italic>\n 2<\/jats:sub>\n form a Hamiltonian cycle and 0 otherwise. Motivated by applications for the Hamiltonicity problem, we show that\n H<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n has rank exactly 2\n \n t<\/jats:italic>\n \/2\u22121\n <\/jats:sup>\n over GF(2). The upper bound is established by an explicit factorization of\n H<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n as the product of two submatrices; the matchings labeling columns and rows, respectively, of the submatrices therefore form a basis\n X<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n of\n H<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n . The lower bound follows because the 2\n \n t<\/jats:italic>\n \/2\u22121\n <\/jats:sup>\n \u00d7 2\n \n t<\/jats:italic>\n \/2\u22121\n <\/jats:sup>\n submatrix with rows and columns labeled by\n X<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n can be seen to have full rank.\n <\/jats:p>\n \n We obtain several algorithmic results based on the rank of\n H<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n and the particular structure of the matchings in\n X<\/jats:bold>\n \n t<\/jats:italic>\n <\/jats:sub>\n . First, we present a 1.888\n \n n<\/jats:italic>\n <\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n time Monte Carlo algorithm that solves the Hamiltonicity problem in directed bipartite graphs. Second, we give a Monte Carlo algorithm that solves the problem in (2 + \u221a 2)\n pw<\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n time when provided with a path decomposition of width pw for the input graph. Moreover, we show that this algorithm is best possible under the Strong Exponential Time Hypothesis, in the sense that an algorithm with running time (2 + \u221a2 \u2212 \u03f5)\n pw<\/jats:sup>\n n<\/jats:italic>\n \n O<\/jats:italic>\n (1)\n <\/jats:sup>\n , for any \u03f5 > 0, would imply the breakthrough result of a (2 \u2212 \u03f5\n \u2032<\/jats:sup>\n )\n \n n<\/jats:italic>\n <\/jats:sup>\n -time algorithm for CNF-Sat for some \u03f5\n \u2032<\/jats:sup>\n > 0.\n <\/jats:p>","DOI":"10.1145\/3148227","type":"journal-article","created":{"date-parts":[[2018,3,14]],"date-time":"2018-03-14T12:34:20Z","timestamp":1521030860000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Fast Hamiltonicity Checking Via Bases of Perfect Matchings"],"prefix":"10.1145","volume":"65","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2472-2975","authenticated-orcid":false,"given":"Marek","family":"Cygan","sequence":"first","affiliation":[{"name":"University of Warsaw, Banacha, Warszawa"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0193-7239","authenticated-orcid":false,"given":"Stefan","family":"Kratsch","sequence":"additional","affiliation":[{"name":"Max-Planck Institute for Informatics, Bonn"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesper","family":"Nederlof","sequence":"additional","affiliation":[{"name":"Utrecht University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/290179.290180"},{"key":"e_1_2_1_2_1","volume-title":"Computational Complexity - A Modern Approach","author":"Arora Sanjeev"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(93)90033-6"},{"key":"e_1_2_1_4_1","volume-title":"Combinatorial processes and dynamic programming","author":"Bellman Richard E."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/321105.321111"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-009-9185-7"},{"key":"e_1_2_1_8_1","volume-title":"Treewidth: Structure and algorithms","author":"Bodlaender Hans L.","year":"2007"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11409-0_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2925416"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.23"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2012.02.004"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.3230010302"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00137"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9133-3"},{"key":"e_1_2_1_20_1","volume-title":"Fomin and Dieter Kratsch","author":"Fedor","year":"2010"},{"key":"e_1_2_1_21_1","article-title":"Enumerating all hamilton cycles and bounding the number of Hamilton cycles in 3-regular graphs","volume":"18","author":"Gebauer Heidi","year":"2011","journal-title":"Electr. J. Comb."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993806.1993829"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800029.808532"},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"Branch and tree decomposition techniques for discrete optimization","volume":"2005","author":"Hicks Illya V.","year":"2005","journal-title":"Tutorials Oper Res"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394650.2394663"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(82)90044-X"},{"key":"e_1_2_1_28_1","volume-title":"Algorithm Design","author":"Kleinberg Jon","year":"2006"},{"key":"e_1_2_1_29_1","volume-title":"Lecture Notes in Computer Science","author":"Kloks Ton"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/800179.810218"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.21.2.498"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133097"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579206"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","volume-title":"Invitation to Fixed-Parameter Algorithms","author":"Niedermeier Rolf","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873687"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192528"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_38_1","volume-title":"Combinatorial Optimization (Lecture Notes in Computer Science), Michael J\u00fcnger","author":"Woeginger Gerhard J."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3148227","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3148227","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:02Z","timestamp":1750212662000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3148227"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,13]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2018,6,30]]}},"alternative-id":["10.1145\/3148227"],"URL":"https:\/\/doi.org\/10.1145\/3148227","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,3,13]]},"assertion":[{"value":"2015-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-03-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}