{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T09:59:00Z","timestamp":1773482340616,"version":"3.50.1"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,7,15]],"date-time":"2021-07-15T00:00:00Z","timestamp":1626307200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"crossref","award":["1176\/18"],"award-info":[{"award-number":["1176\/18"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"crossref"}]},{"name":"National Science Foundation","award":["2008838"],"award-info":[{"award-number":["2008838"]}]},{"name":"Swarnajayanti Fellowship","award":["DST\/SJF\/MSA-01\/2017-18"],"award-info":[{"award-number":["DST\/SJF\/MSA-01\/2017-18"]}]},{"name":"United States\u2013Israel Binational Science Foundation","award":["2018302"],"award-info":[{"award-number":["2018302"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2021,7,31]]},"abstract":"<jats:p>\n            Recently, Brand et\u00a0al.\u00a0[STOC 2018] gave a\n            <jats:italic>randomized<\/jats:italic>\n            mathcal O(4\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n            <\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            \u03b5\n            <jats:sup>-2<\/jats:sup>\n            -time exponential-space algorithm to approximately compute the number of paths on\n            <jats:italic>k<\/jats:italic>\n            vertices in a graph\n            <jats:italic>G<\/jats:italic>\n            up to a multiplicative error of 1 \u00b1 \u03b5 based on exterior algebra. Prior to our work, this has been the state-of-the-art. In this article, we revisit the algorithm by Alon and Gutner\u00a0[IWPEC 2009, TALG 2010], and obtain the following results:\n          <\/jats:p>\n          <jats:p>\n            \u2022 We present a\n            <jats:italic>deterministic<\/jats:italic>\n            4\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              +\n              <jats:italic>O<\/jats:italic>\n              (\u221a\n              <jats:italic>k<\/jats:italic>\n              (log\n              <jats:italic>k<\/jats:italic>\n              +log\n              <jats:sup>2<\/jats:sup>\n              \u03b5\n              <jats:sup>-1<\/jats:sup>\n              ))\n            <\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            -time\n            <jats:italic>polynomial-space<\/jats:italic>\n            algorithm. This\n            <jats:italic>matches<\/jats:italic>\n            the running time of the best known deterministic polynomial-space algorithm for\n            <jats:italic>deciding<\/jats:italic>\n            whether a given graph\n            <jats:italic>G<\/jats:italic>\n            has a path on\n            <jats:italic>k<\/jats:italic>\n            vertices.\n          <\/jats:p>\n          <jats:p>\n            \u2022 Additionally, we present a\n            <jats:italic>randomized<\/jats:italic>\n            4\n            <jats:sup>\n              <jats:italic>k<\/jats:italic>\n              +mathcal O(log\n              <jats:italic>k<\/jats:italic>\n              (log\n              <jats:italic>k<\/jats:italic>\n              +log\u03b5\n              <jats:sup>-1<\/jats:sup>\n              ))\n            <\/jats:sup>\n            <jats:italic>m<\/jats:italic>\n            -time\n            <jats:italic>polynomial-space<\/jats:italic>\n            algorithm. Our algorithm is simple\u2014we only make elementary use of the probabilistic method.\n          <\/jats:p>\n          <jats:p>\n            Here,\n            <jats:italic>n<\/jats:italic>\n            and\n            <jats:italic>m<\/jats:italic>\n            are the number of vertices and the number of edges, respectively. Additionally, our approach extends to approximate counting of other patterns of small size (such as\n            <jats:italic>q<\/jats:italic>\n            -dimensional\n            <jats:italic>p<\/jats:italic>\n            -matchings).\n          <\/jats:p>","DOI":"10.1145\/3461477","type":"journal-article","created":{"date-parts":[[2021,7,16]],"date-time":"2021-07-16T05:26:33Z","timestamp":1626413193000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Approximate Counting of\n            <i>k<\/i>\n            -Paths: Simpler, Deterministic, and in Polynomial Space"],"prefix":"10.1145","volume":"17","author":[{"given":"Daniel","family":"Lokshtanov","sequence":"first","affiliation":[{"name":"Lund University, Sweden"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andreas","family":"Bj\u00d6rklund","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, United Stated"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Saket","family":"Saurabh","sequence":"additional","affiliation":[{"name":"The Institute for Mathematical Sciences, HBNI and University of Bergen, Norway"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Meirav","family":"Zehavi","sequence":"additional","affiliation":[{"name":"Ben-Gurion University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,7,15]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Marek Cygan Fedor V. Fomin Danny Hermelin and Magnus Wahlstr\u00f6m. [n.d.]. Randomization in Parameterized Complexity. Dagstuhl. Retrieved from www.dagstuhl.de\/de\/programm\/kalender\/semhp\/?semnr=17041.  Marek Cygan Fedor V. Fomin Danny Hermelin and Magnus Wahlstr\u00f6m. [n.d.]. Randomization in Parameterized Complexity. Dagstuhl. Retrieved from www.dagstuhl.de\/de\/programm\/kalender\/semhp\/?semnr=17041."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btn163"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11269-0_1"},{"key":"e_1_2_1_4_1","article-title":"Balanced families of perfect hash functions and their applications","volume":"6","author":"Alon Noga","year":"2010","unstructured":"Noga Alon and Shai Gutner . 2010 . Balanced families of perfect hash functions and their applications . ACM Trans. Algor. 6 , 3 (2010), 54:1\u201354:12. Noga Alon and Shai Gutner. 2010. Balanced families of perfect hash functions and their applications. ACM Trans. Algor. 6, 3 (2010), 54:1\u201354:12.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_5_1","volume-title":"Spencer","author":"Alon Noga","year":"2016","unstructured":"Noga Alon and Joel H . Spencer . 2016 . The Probabilistic Method (4th ed.). Wiley Publishing . Noga Alon and Joel H. Spencer. 2016. The Probabilistic Method (4th ed.). Wiley Publishing."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/646345.690043"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.106"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/110839229"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_52"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2017.03.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1048975"},{"key":"e_1_2_1_13_1","article-title":"Counting thin subgraphs via packings faster than meet-in-the-middle time","volume":"13","author":"Bj\u00f6rklund Andreas","year":"2017","unstructured":"Andreas Bj\u00f6rklund , Petteri Kaski , and Lukasz Kowalik . 2017 . Counting thin subgraphs via packings faster than meet-in-the-middle time . ACM Trans. Algor. 13 , 4 (2017), 48:1\u201348:26. Andreas Bj\u00f6rklund, Petteri Kaski, and Lukasz Kowalik. 2017. Counting thin subgraphs via packings faster than meet-in-the-middle time. ACM Trans. Algor. 13, 4 (2017), 48:1\u201348:26.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_14_1","volume-title":"Extensor-coding. In Proceedings of the 50th ACM SIGACT Symposium on Theory of Computing. 151\u2013164","author":"Brand Cornelius","year":"2018","unstructured":"Cornelius Brand , Holger Dell , and Thore Husfeldt . 2018 . Extensor-coding. In Proceedings of the 50th ACM SIGACT Symposium on Theory of Computing. 151\u2013164 . Cornelius Brand, Holger Dell, and Thore Husfeldt. 2018. Extensor-coding. In Proceedings of the 50th ACM SIGACT Symposium on Theory of Computing. 151\u2013164."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/080716475"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.22"},{"key":"e_1_2_1_18_1","volume-title":"Parameterized Algorithms","author":"Cygan Marek","unstructured":"Marek Cygan , Fedor V. Fomin , Lukasz Kowalik , Daniel Lokshtanov , D\u00e1niel Marx , Marcin Pilipczuk , Michal Pilipczuk , and Saket Saurabh . 2015. Parameterized Algorithms . Springer . Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, D\u00e1niel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. 2015. Parameterized Algorithms. Springer."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2007.0172"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47672-7_40"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2886094"},{"key":"e_1_2_1_23_1","volume-title":"Kernelization: Theory of Parameterized Preprocessing","author":"Fomin Fedor V.","year":"2019","unstructured":"Fedor V. Fomin , Daniel Lokshtanov , Saket Saurabh , and Meirav Zehavi . 2019 . Kernelization: Theory of Parameterized Preprocessing . Cambridge University Press . Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Meirav Zehavi. 2019. Kernelization: Theory of Parameterized Preprocessing. Cambridge University Press."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2018.01.004"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118777.3119179"},{"key":"e_1_2_1_26_1","volume-title":"Extremal Combinatorics: With Applications in Computer Science","author":"Jukna Stasys","year":"2010","unstructured":"Stasys Jukna . 2010 . Extremal Combinatorics: With Applications in Computer Science ( 1 st ed.). Springer Publishing Company, Inc orporated. Stasys Jukna. 2010. Extremal Combinatorics: With Applications in Computer Science (1st ed.). Springer Publishing Company, Incorporated.","edition":"1"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_47"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2742544"},{"key":"e_1_2_1_29_1","article-title":"LIMITS and applications of group algebras for parameterized problems","volume":"12","author":"Koutis Ioannis","year":"2016","unstructured":"Ioannis Koutis and Ryan Williams . 2016 . LIMITS and applications of group algebras for parameterized problems . ACM Trans. Algor. 12 , 3 (2016), 31:1\u201331:18. Ioannis Koutis and Ryan Williams. 2016. LIMITS and applications of group algebras for parameterized problems. ACM Trans. Algor. 12, 3 (2016), 31:1\u201331:18.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25870-1_24"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806735"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"R. Milo S. Shen-Orr S. Itzkovitz N. Kashtan D. Chklovskii and U. Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 (2002) 824\u2013827. Retrieved from http:\/\/science.sciencemag.org\/content\/298\/5594\/824.  R. Milo S. Shen-Orr S. Itzkovitz N. Kashtan D. Chklovskii and U. Alon. 2002. Network motifs: Simple building blocks of complex networks. Science 298 5594 (2002) 824\u2013827. Retrieved from http:\/\/science.sciencemag.org\/content\/298\/5594\/824.","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_2_1_33_1","volume-title":"Probability and Computing\u2014Randomized Algorithms and Probabilistic Analysis","author":"Mitzenmacher Michael","unstructured":"Michael Mitzenmacher and Eli Upfal . 2005. Probability and Computing\u2014Randomized Algorithms and Probabilistic Analysis . Cambridge University Press . Michael Mitzenmacher and Eli Upfal. 2005. Probability and Computing\u2014Randomized Algorithms and Probabilistic Analysis. Cambridge University Press."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1995.492475"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2006.13.133"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.11.008"},{"key":"e_1_2_1_37_1","volume-title":"Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24 (05","author":"Sharan Roded","year":"2006","unstructured":"Roded Sharan and Trey Ideker . 2006. Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24 (05 2006 ), 427\u201333. Roded Sharan and Trey Ideker. 2006. Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24 (05 2006), 427\u201333."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-7-199"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.04.024"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.11.004"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/09076619X"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-48350-3_86"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461477","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3461477","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:28:35Z","timestamp":1750195715000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3461477"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,15]]},"references-count":42,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,7,31]]}},"alternative-id":["10.1145\/3461477"],"URL":"https:\/\/doi.org\/10.1145\/3461477","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,7,15]]},"assertion":[{"value":"2019-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-07-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}