{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,1]],"date-time":"2026-03-01T05:46:16Z","timestamp":1772343976030,"version":"3.50.1"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2017,9,19]],"date-time":"2017-09-19T00:00:00Z","timestamp":1505779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["N206 567140 and 2013\/09\/B\/ST6\/03136"],"award-info":[{"award-number":["N206 567140 and 2013\/09\/B\/ST6\/03136"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002341","name":"Suomen Akatemia","doi-asserted-by":"publisher","award":["252083, 256287, and 283437"],"award-info":[{"award-number":["252083, 256287, and 283437"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5det","doi-asserted-by":"publisher","award":["VR 2012-4730"],"award-info":[{"award-number":["VR 2012-4730"]}],"id":[{"id":"10.13039\/501100004359","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":[[2017,10,31]]},"abstract":"<jats:p>\n            Vassilevska and Williams (STOC\u201909) showed how to count simple paths on\n            <jats:italic>k<\/jats:italic>\n            vertices and matchings on\n            <jats:italic>k<\/jats:italic>\n            \/2 edges in an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              \/2+\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            . In the same year, two different algorithms with the same runtime were given by Koutis and Williams (ICALP\u201909), and Bj\u00f6rklund et al. (ESA\u201909), via\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              <jats:italic>st<\/jats:italic>\n              \/2+\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            -time algorithms for counting\n            <jats:italic>t<\/jats:italic>\n            -tuples of pairwise disjoint sets drawn from a given family of\n            <jats:italic>s<\/jats:italic>\n            -sized subsets of an\n            <jats:italic>n<\/jats:italic>\n            -element universe. Shortly afterwards, Alon and Gutner (TALG\u201910) showed that these problems have \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u230a\n              <jats:italic>st<\/jats:italic>\n              \/2\u230b\n            <\/jats:sup>\n            ) and \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              \u230a\n              <jats:italic>k<\/jats:italic>\n              \/2\u230b\n            <\/jats:sup>\n            ) lower bounds when counting by color coding.\n          <\/jats:p>\n          <jats:p>\n            Here, we show that one can do better\u2014we show that the \u201cmeet-in-the-middle\u201d exponent\n            <jats:italic>st<\/jats:italic>\n            \/2 can be beaten and give an algorithm that counts in time\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              0.45470382\n              <jats:italic>st<\/jats:italic>\n              +\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            for\n            <jats:italic>t<\/jats:italic>\n            a multiple of three. This implies algorithms for counting occurrences of a fixed subgraph on\n            <jats:italic>k<\/jats:italic>\n            vertices and pathwidth\n            <jats:italic>p<\/jats:italic>\n            \u226a\n            <jats:italic>k<\/jats:italic>\n            in an\n            <jats:italic>n<\/jats:italic>\n            -vertex graph in\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>\n              0.45470382\n              <jats:italic>k<\/jats:italic>\n              +2\n              <jats:italic>p<\/jats:italic>\n              +\n              <jats:italic>O<\/jats:italic>\n              (1)\n            <\/jats:sup>\n            time, improving on the three mentioned algorithms for paths and matchings, and circumventing the color-coding lower bound. We also give improved bounds for counting\n            <jats:italic>t<\/jats:italic>\n            -tuples of disjoint\n            <jats:italic>s<\/jats:italic>\n            -sets for\n            <jats:italic>s<\/jats:italic>\n            = 2,3,4.\n          <\/jats:p>\n          <jats:p>Our algorithms use fast matrix multiplication. We show an argument that this is necessary to go below the meet-in-the-middle barrier.<\/jats:p>","DOI":"10.1145\/3125500","type":"journal-article","created":{"date-parts":[[2017,9,20]],"date-time":"2017-09-20T12:35:19Z","timestamp":1505910919000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Counting Thin Subgraphs via Packings Faster than Meet-in-the-Middle Time"],"prefix":"10.1145","volume":"13","author":[{"given":"Andreas","family":"Bj\u00f6rklund","sequence":"first","affiliation":[{"name":"Department of Computer Science, Lund University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[{"name":"Helsinki Institute for Information Technology HIIT, Department of Information and Computer Science, Aalto University, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0141ukasz","family":"Kowalik","sequence":"additional","affiliation":[{"name":"Institute of Informatics, University of Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,9,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1798596.1798607"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/100789403"},{"key":"e_1_2_1_3_1","first-page":"565","article-title":"Sylvester\u2019s identity and multistep integer-preserving gaussian elimination","volume":"22","author":"Bareiss Erwin H.","year":"1968","unstructured":"Erwin H. Bareiss . 1968 . Sylvester\u2019s identity and multistep integer-preserving gaussian elimination . Math. Comp. 22 , 565 -- 578 . 0025-5718 Erwin H. Bareiss. 1968. Sylvester\u2019s identity and multistep integer-preserving gaussian elimination. Math. Comp. 22, 565--578. 0025-5718","journal-title":"Math. Comp."},{"key":"e_1_2_1_4_1","unstructured":"Andreas Bj\u00f6rklund. 2012. Below all subsets for some permutational counting problems. CoRR abs\/1211.0391.  Andreas Bj\u00f6rklund. 2012. Below all subsets for some permutational counting problems. CoRR abs\/1211.0391."},{"key":"e_1_2_1_5_1","unstructured":"Andreas Bj\u00f6rklund Thore Husfeldt Petteri Kaski and Mikko Koivisto. 2008. The fast intersection transform with applications to counting paths. CoRR abs\/0809.2489.  Andreas Bj\u00f6rklund Thore Husfeldt Petteri Kaski and Mikko Koivisto. 2008. The fast intersection transform with applications to counting paths. CoRR abs\/0809.2489."},{"key":"e_1_2_1_6_1","volume-title":"ESA (Lecture Notes in Computer Science)","author":"Bj\u00f6rklund Andreas","unstructured":"Andreas Bj\u00f6rklund , Thore Husfeldt , Petteri Kaski , and Mikko Koivisto . 2009. Counting paths and packings in halves . In ESA (Lecture Notes in Computer Science) , Amos Fiat and Peter Sanders (Eds.), Vol. 5757 . Springer , Berlin , 578--586. Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, and Mikko Koivisto. 2009. Counting paths and packings in halves. In ESA (Lecture Notes in Computer Science), Amos Fiat and Peter Sanders (Eds.), Vol. 5757. Springer, Berlin, 578--586."},{"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":"Fast zeta transforms for lattices with few irreducibles","author":"Bj\u00f6rklund Andreas","unstructured":"Andreas Bj\u00f6rklund , Thore Husfeldt , Petteri Kaski , Mikko Koivisto , Jesper Nederlof , and Pekka Parviainen . 2012. Fast zeta transforms for lattices with few irreducibles . In SODA, Yuval Rabani (Ed.). SIAM , 1436--1444. Andreas Bj\u00f6rklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto, Jesper Nederlof, and Pekka Parviainen. 2012. Fast zeta transforms for lattices with few irreducibles. In SODA, Yuval Rabani (Ed.). SIAM, 1436--1444."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39206-1_30"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.22"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00017-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2011.10.001"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.11.006"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321823"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90234-M"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00047-8"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_54"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859798"},{"key":"e_1_2_1_24_1","volume-title":"Tensors: Geometry and Applications. Graduate Studies in Mathematics","author":"Landsberg J. M.","year":"2012","unstructured":"J. M. Landsberg . 2012 . Tensors: Geometry and Applications. Graduate Studies in Mathematics , Vol. 128 . American Mathematical Society , Providence, RI . xx+439 pages. J. M. Landsberg. 2012. Tensors: Geometry and Applications. Graduate Studies in Mathematics, Vol. 128. American Mathematical Society, Providence, RI. xx+439 pages."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.80"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Fran\u00e7ois Le Gall. 2014. Powers of Tensors and Fast Matrix Multiplication. arXiv:1401.7714.  Fran\u00e7ois Le Gall. 2014. Powers of Tensors and Fast Matrix Multiplication. arXiv:1401.7714.","DOI":"10.1145\/2608628.2608664"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90054-3"},{"key":"e_1_2_1_28_1","first-page":"415","article-title":"On the complexity of the subgraph problem","volume":"26","author":"Ne\u0161et\u0159il J.","year":"1985","unstructured":"J. Ne\u0161et\u0159il and S. Poljak . 1985 . On the complexity of the subgraph problem . Comment. Math. Univ. Carolin. 26 , 2, 415 -- 419 . CMUCAA0010-2628 J. Ne\u0161et\u0159il and S. Poljak. 1985. On the complexity of the subgraph problem. Comment. Math. Univ. Carolin. 26, 2, 415--419. CMUCAA0010-2628","journal-title":"Comment. Math. Univ. Carolin."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/1026076"},{"key":"e_1_2_1_30_1","unstructured":"Victor Y. Pan. 2014. Matrix multiplication trilinear decompositions APA algorithms and summation. CoRR abs\/1412.1145. http:\/\/arxiv.org\/abs\/1412.1145  Victor Y. Pan. 2014. Matrix multiplication trilinear decompositions APA algorithms and summation. CoRR abs\/1412.1145. http:\/\/arxiv.org\/abs\/1412.1145"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536477"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125500","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3125500","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:23Z","timestamp":1750212683000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3125500"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,9,19]]},"references-count":32,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10,31]]}},"alternative-id":["10.1145\/3125500"],"URL":"https:\/\/doi.org\/10.1145\/3125500","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,9,19]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-09-19","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}