{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:16:06Z","timestamp":1750220166925,"version":"3.41.0"},"reference-count":39,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,31]],"date-time":"2023-01-31T00:00:00Z","timestamp":1675123200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ERC Consolidator","award":["863438"],"award-info":[{"award-number":["863438"]}]},{"name":"NSF-BSF","award":["20196"],"award-info":[{"award-number":["20196"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,1,31]]},"abstract":"<jats:p>Since counting subgraphs in general graphs is, by and large, a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family that has been extensively studied is that of graphs of bounded degeneracy (e.g., planar graphs). This line of work, which started in the early 80\u2019s, culminated in a recent work of Gishboliner et\u00a0al., which highlighted the importance of the task of counting homomorphic copies of cycles (i.e., cyclic walks) in graphs of bounded degeneracy.<\/jats:p>\n          <jats:p>\n            Our main result in this paper is a surprisingly tight relation between the above task and the well-studied problem of\n            <jats:italic>detecting (standard) copies<\/jats:italic>\n            of directed cycles in\n            <jats:italic>general directed<\/jats:italic>\n            graphs. More precisely, we prove the following:\n            <jats:list list-type=\"bullet\">\n              <jats:list-item>\n                <jats:p>\n                  One can compute the number of homomorphic copies of\n                  <jats:italic>\n                    C\n                    <jats:sub>2k<\/jats:sub>\n                  <\/jats:italic>\n                  and\n                  <jats:italic>\n                    C\n                    <jats:sub>2k+1<\/jats:sub>\n                  <\/jats:italic>\n                  in\n                  <jats:italic>n<\/jats:italic>\n                  -vertex graphs of bounded degeneracy in time O\u0303(\n                  <jats:italic>\n                    n\n                    <jats:sup>\n                      d\n                      <jats:sub>k<\/jats:sub>\n                    <\/jats:sup>\n                  <\/jats:italic>\n                  ), where the fastest\n                  <jats:italic>known<\/jats:italic>\n                  algorithm for detecting directed copies of\n                  <jats:italic>\n                    C\n                    <jats:sub>k<\/jats:sub>\n                  <\/jats:italic>\n                  in general\n                  <jats:italic>m<\/jats:italic>\n                  -edge digraphs runs in time O\u0303(\n                  <jats:italic>\n                    m\n                    <jats:sup>\n                      d\n                      <jats:sub>k<\/jats:sub>\n                    <\/jats:sup>\n                  <\/jats:italic>\n                  ).\n                <\/jats:p>\n              <\/jats:list-item>\n              <jats:list-item>\n                <jats:p>\n                  Conversely, one can transform any\n                  <jats:italic>\n                    O(n\n                    <jats:sup>\n                      b\n                      <jats:sub>k<\/jats:sub>\n                    <\/jats:sup>\n                    )\n                  <\/jats:italic>\n                  algorithm for computing the number of homomorphic copies of\n                  <jats:italic>\n                    C\n                    <jats:sub>2k<\/jats:sub>\n                  <\/jats:italic>\n                  or of\n                  <jats:italic>\n                    C\n                    <jats:sub>2k+1<\/jats:sub>\n                  <\/jats:italic>\n                  in\n                  <jats:italic>n<\/jats:italic>\n                  -vertex graphs of bounded degeneracy, into an O\u0303(\n                  <jats:italic>\n                    m\n                    <jats:sup>\n                      b\n                      <jats:sub>k<\/jats:sub>\n                    <\/jats:sup>\n                  <\/jats:italic>\n                  ) time algorithm for detecting directed copies of\n                  <jats:italic>\n                    C\n                    <jats:sub>k<\/jats:sub>\n                  <\/jats:italic>\n                  in general\n                  <jats:italic>m<\/jats:italic>\n                  -edge digraphs.\n                <\/jats:p>\n              <\/jats:list-item>\n            <\/jats:list>\n          <\/jats:p>\n          <jats:p>\n            We emphasize that our first result does not use a black-box reduction (as opposed to the second result which does). Instead, we design an algorithm for computing the number of\n            <jats:italic>\n              C\n              <jats:sub>k<\/jats:sub>\n            <\/jats:italic>\n            -homomorphisms in degenerate graphs and show that one part of its\n            <jats:italic>analysis<\/jats:italic>\n            can be reduced to the analysis of the fastest known algorithm for detecting directed cycles in general digraphs, which was carried out in a recent breakthrough of Dalirrooyfard, Vuong and Vassilevska Williams. As a by-product of our algorithm, we obtain a new algorithm for detecting\n            <jats:italic>k<\/jats:italic>\n            -cycles in directed and undirected graphs of bounded degeneracy that is faster than all previously known algorithms for 7 \u2264\n            <jats:italic>k<\/jats:italic>\n            \u2264 11, and faster for all\n            <jats:italic>k<\/jats:italic>\n            \u2265 7 if the matrix multiplication exponent is 2.\n          <\/jats:p>","DOI":"10.1145\/3560820","type":"journal-article","created":{"date-parts":[[2022,9,6]],"date-time":"2022-09-06T11:53:46Z","timestamp":1662465226000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Counting Homomorphic Cycles in Degenerate Graphs"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0688-8111","authenticated-orcid":false,"given":"Lior","family":"Gishboliner","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Z\u00fcrich, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1494-7604","authenticated-orcid":false,"given":"Yevgeny","family":"Levanzov","sequence":"additional","affiliation":[{"name":"School of Mathematics, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9902-0164","authenticated-orcid":false,"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[{"name":"School of Mathematics, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7550-6506","authenticated-orcid":false,"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[{"name":"Department of Mathematics, University of Haifa, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,20]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Proc. 55th Annual IEEE Symposium on Foundations of Computer Science","author":"Abboud A.","year":"2014","unstructured":"A. Abboud and V. Vassilevska Williams. 2014. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science."},{"key":"e_1_3_3_3_2","first-page":"522","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Alman J.","unstructured":"J. Alman and V. Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 522\u2013539."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_3_7_2","first-page":"1","article-title":"Counting subgraphs in degenerate graphs","author":"Bera S. K.","year":"2022","unstructured":"S. K. Bera, L. Gishboliner, Y. Levanzov, C. Seshadhri, and A. Shapira. 2022. Counting subgraphs in degenerate graphs. ACM Journal of the ACM (JACM) 69, 3 (2022), 1\u201321.","journal-title":"ACM Journal of the ACM (JACM)"},{"key":"e_1_3_3_8_2","first-page":"38:1\u201338:20","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920)","author":"Bera S. K.","unstructured":"S. K. Bera, N. Pashanasangi, and C. Seshadhri. Linear time subgraph counting, graph degeneracy, and the chasm at size six. In Proceedings of the 11th Innovations in Theoretical Computer Science Conference (ITCS\u201920). 38:1\u201338:20."},{"key":"e_1_3_3_9_2","first-page":"2315","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Bera S. K.","unstructured":"S. K. Bera, N. Pashanasangi, and C. Seshadhri. Near-linear time homomorphism counting in bounded degeneracy graphs: the barrier of long induced cycles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics, 2315\u20132332."},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01904851"},{"key":"e_1_3_3_11_2","first-page":"1","article-title":"Faster algorithms for counting subgraphs in sparse graphs","author":"Bressan M.","year":"2021","unstructured":"M. Bressan. 2021. Faster algorithms for counting subgraphs in sparse graphs. Algorithmica. 1\u201328.","journal-title":"Algorithmica"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_3_3_14_2","first-page":"130","volume-title":"Proc. 55th Annual IEEE Symposium on Foundations of Computer Science","author":"Curticapean R.","year":"2014","unstructured":"R. Curticapean and D. Marx. 2014. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In Proc. 55th Annual IEEE Symposium on Foundations of Computer Science. 130\u2013139."},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316329"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00252-7"},{"key":"e_1_3_3_18_2","first-page":"165","article-title":"Strong independence of graphcopy functions","author":"Erd\u0151s P.","year":"1979","unstructured":"P. Erd\u0151s, L. Lov\u00e1sz, and J. Spencer. 1979. Strong independence of graphcopy functions. Graph Theory and Related Topics. 165\u2013172.","journal-title":"Graph Theory and Related Topics"},{"key":"e_1_3_3_19_2","first-page":"538","volume-title":"Proc. 43rd IEEE Symposium on Foundations of Computer Science","author":"Flum J.","year":"2002","unstructured":"J. Flum and M. Grohe. 2002. The parameterized complexity of counting problems. In Proc. 43rd IEEE Symposium on Foundations of Computer Science. 538\u2013547."},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/1206035.1206036"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcom.1998.0476"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175350"},{"key":"e_1_3_3_24_2","first-page":"296","volume-title":"International Symposium on Symbolic and Algebraic Computation (ISSAC\u201914)","author":"Gall F. Le","year":"2014","unstructured":"F. Le Gall. 2014. Powers of tensors and fast matrix multiplication. In International Symposium on Symbolic and Algebraic Computation (ISSAC\u201914). 296\u2013303"},{"key":"e_1_3_3_25_2","article-title":"Large networks and graph limits","author":"Lov\u00e1sz L.","year":"2012","unstructured":"L. Lov\u00e1sz. 2012. Large networks and graph limits. Providence: American Mathematical Society.","journal-title":"Providence: American Mathematical Society"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.27"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.06.019"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_3_30_2","article-title":"How to find long paths efficiently","author":"Monien B.","year":"1985","unstructured":"B. Monien. 1985. How to find long paths efficiently. Annals of Discrete Mathematics 25, 239\u2013254.","journal-title":"Annals of Discrete Mathematics"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/2230458"},{"key":"e_1_3_3_32_2","article-title":"On the complexity of the subgraph problem","author":"Ne\u0161et\u0159il J.","year":"1985","unstructured":"J. Ne\u0161et\u0159il and S. Poljak. 1985. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26, 2 (1985), 415\u2013419.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1090\/pcms\/010"},{"key":"e_1_3_3_35_2","article-title":"Efficient algorithms for clique problems","author":"Williams V. Vassilevska","year":"2009","unstructured":"V. Vassilevska Williams. 2009. Efficient algorithms for clique problems. Information Processing Letters 109, 4 (2009), 254\u2013257.","journal-title":"Information Processing Letters"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_3_37_2","volume-title":"Proc. 41st Annual ACM Symposium on the Theory of Computing","author":"Williams V. Vassilevska","year":"2009","unstructured":"V. Vassilevska Williams and R. Williams. 2009. Finding, minimizing, and counting weighted subgraphs. In Proc. 41st Annual ACM Symposium on the Theory of Computing. 455\u2013464."},{"key":"e_1_3_3_38_2","article-title":"Finding heaviest  \\(H\\) -subgraphs in real weighted graphs, with applications","author":"Williams V. Vassilevska","year":"2010","unstructured":"V. Vassilevska Williams, R. Williams, and R. Yuster. 2010. Finding heaviest \\(H\\) -subgraphs in real weighted graphs, with applications. ACM Transactions on Algorithms (TALG) 6, 3 (2010), 1\u201323.","journal-title":"ACM Transactions on Algorithms (TALG)"},{"key":"e_1_3_3_39_2","volume-title":"SODA","author":"Yuster R.","year":"2004","unstructured":"R. Yuster and U. Zwick. 2004. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. In SODA, vol. 4. 254\u2013260."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194274133"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3560820","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3560820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:00:34Z","timestamp":1750186834000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3560820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,31]]},"references-count":39,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1,31]]}},"alternative-id":["10.1145\/3560820"],"URL":"https:\/\/doi.org\/10.1145\/3560820","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2023,1,31]]},"assertion":[{"value":"2021-10-28","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}