{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T22:39:07Z","timestamp":1789684747404,"version":"4.0.1"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2022,6,29]],"date-time":"2022-06-29T00:00:00Z","timestamp":1656460800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF TRIPODS","award":["CCF-1740850, CCF-1813165, CCF-1909790, and W911NF1910294"],"award-info":[{"award-number":["CCF-1740850, CCF-1813165, CCF-1909790, and W911NF1910294"]}]},{"name":"ERC","award":["633509"],"award-info":[{"award-number":["633509"]}]},{"name":"ISF","award":["1028\/16"],"award-info":[{"award-number":["1028\/16"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2022,6,30]]},"abstract":"<jats:p>\n            We consider the problem of counting the number of copies of a fixed graph\n            <jats:italic>H<\/jats:italic>\n            within an input graph\n            <jats:italic>G<\/jats:italic>\n            . This is one of the most well-studied algorithmic graph problems, with many theoretical and practical applications. We focus on solving this problem when the input\n            <jats:italic>G<\/jats:italic>\n            has\n            <jats:italic>bounded degeneracy<\/jats:italic>\n            . This is a rich family of graphs, containing all graphs without a fixed minor (e.g., planar graphs), as well as graphs generated by various random processes (e.g., preferential attachment graphs). We say that\n            <jats:italic>H<\/jats:italic>\n            is\n            <jats:italic>easy<\/jats:italic>\n            if there is a linear-time algorithm for counting the number of copies of\n            <jats:italic>H<\/jats:italic>\n            in an input\n            <jats:italic>G<\/jats:italic>\n            of bounded degeneracy. A seminal result of Chiba and Nishizeki from \u201985 states that every\n            <jats:italic>H<\/jats:italic>\n            on at most 4 vertices is easy. Bera, Pashanasangi, and Seshadhri recently extended this to all\n            <jats:italic>H<\/jats:italic>\n            on 5 vertices and further proved that for every\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( k \\gt 5 \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            there is a\n            <jats:italic>k<\/jats:italic>\n            -vertex\n            <jats:italic>H<\/jats:italic>\n            which is not easy. They left open the natural problem of characterizing all easy graphs\n            <jats:italic>H<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            Bressan has recently introduced a framework for counting subgraphs in degenerate graphs, from which one can extract a sufficient condition for a graph\n            <jats:italic>H<\/jats:italic>\n            to be easy. Here, we show that this sufficient condition is also necessary, thus fully answering the Bera\u2013Pashanasangi\u2013Seshadhri problem. We further resolve two closely related problems; namely characterizing the graphs that are easy with respect to counting induced copies, and with respect to counting homomorphisms.\n          <\/jats:p>","DOI":"10.1145\/3520240","type":"journal-article","created":{"date-parts":[[2022,3,30]],"date-time":"2022-03-30T11:29:32Z","timestamp":1648639772000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Counting Subgraphs in Degenerate Graphs"],"prefix":"10.1145","volume":"69","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5699-2948","authenticated-orcid":false,"given":"Suman K.","family":"Bera","sequence":"first","affiliation":[{"name":"University of California, Santa Cruz, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lior","family":"Gishboliner","sequence":"additional","affiliation":[{"name":"School of Mathematics, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yevgeny","family":"Levanzov","sequence":"additional","affiliation":[{"name":"School of Mathematics, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"C.","family":"Seshadhri","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Asaf","family":"Shapira","sequence":"additional","affiliation":[{"name":"School of Mathematics, Tel Aviv University, Tel Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,6,29]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"434","volume-title":"Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Abboud A.","unstructured":"A. Abboud and V. Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. 434\u2013443."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210337"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802489"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322389"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aad9029"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_52"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/3125500"},{"key":"e_1_3_3_11_2","first-page":"38:1","volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science Conference.","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. 38:1\u201338:20."},{"key":"e_1_3_3_12_2","first-page":"2315","volume-title":"Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms.","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. 2315\u20132332."},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2983573"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-021-00811-0"},{"key":"e_1_3_3_15_2","first-page":"276","volume-title":"Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201921)","author":"Bressan M.","year":"2021","unstructured":"M. Bressan and M. Roth. 2021. Exact and approximate pattern counting in degenerate graphs: New algorithms, hardness results, and complexity dichotomies. In Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS\u201921). 276\u2013285."},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1086\/421787"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902279"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1137\/0214017"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02125347"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_3_3_21_2","first-page":"130","volume-title":"Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science","author":"Curticapean R.","unstructured":"R. Curticapean and D. Marx. Complexity of counting subgraphs: Only the boundedness of the vertex-cover number counts. In Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science. 130\u2013139."},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316329"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_3_3_25_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_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539703427203"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1086\/224954"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.0030118"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/0207033"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989418"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00047-8"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1137\/110859798"},{"key":"e_1_3_3_34_2","author":"Lov\u00e1sz L.","year":"2012","unstructured":"L. Lov\u00e1sz. 2012. Large Networks and Graph Limits. Providence: American Mathematical Society.","journal-title":"Large Networks and Graph Limits"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.005"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2402.322385"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902283"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.06.019"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.298.5594.824"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.5555\/2230458"},{"issue":"2","key":"e_1_3_3_41_2","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. Commentationes Mathematicae Universitatis Carolinae 26, 2 (1985), 415\u2013419.","journal-title":"Commentationes Mathematicae Universitatis Carolinae"},{"key":"e_1_3_3_42_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btl301"},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bth436"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1090\/pcms\/010"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741640"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741098"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488502"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511987045"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.10.014"},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214056"},{"key":"e_1_3_3_51_2","first-page":"455","volume-title":"Proceedings of the 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 Proceedings of the 41st Annual ACM Symposium on the Theory of Computing. 455\u2013464."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3520240","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3520240","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:10:32Z","timestamp":1750183832000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3520240"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,29]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6,30]]}},"alternative-id":["10.1145\/3520240"],"URL":"https:\/\/doi.org\/10.1145\/3520240","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,29]]},"assertion":[{"value":"2020-12-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-06-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}