{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T05:23:00Z","timestamp":1772601780124,"version":"3.50.1"},"reference-count":33,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T00:00:00Z","timestamp":1613952000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T00:00:00Z","timestamp":1613952000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["Starting Grant DMAP 680153"],"award-info":[{"award-number":["Starting Grant DMAP 680153"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Focused Award \u201cAlgorithms and Learning for AI\u201d","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003407","name":"Ministero dell\u2019Istruzione, dell\u2019Universit\u00e0 e della Ricerca","doi-asserted-by":"publisher","award":["Dipartimenti di Eccellenza 2018-2022"],"award-info":[{"award-number":["Dipartimenti di Eccellenza 2018-2022"]}],"id":[{"id":"10.13039\/501100003407","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Bertinoro International Center for Informatics"},{"DOI":"10.13039\/100012352","name":"Universit\u00e0 degli Studi di Milano","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100012352","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"abstract":"Abstract<\/jats:title>Given a k<\/jats:italic>-node pattern graph H<\/jats:italic> and an n<\/jats:italic>-node host graph G<\/jats:italic>, the subgraph counting problem asks to compute the number of copies of H<\/jats:italic> in G<\/jats:italic>. In this work we address the following question: can we count the copies of H<\/jats:italic> faster if G<\/jats:italic> is sparse? We answer in the affirmative by introducing a novel tree-like decomposition for directed acyclic graphs, inspired by the classic tree decomposition for undirected graphs. This decomposition gives a dynamic program for counting the homomorphisms of H<\/jats:italic> in G<\/jats:italic> by exploiting the degeneracy of G<\/jats:italic>, which allows us to beat the state-of-the-art subgraph counting algorithms when G<\/jats:italic> is sparse enough. For example, we can count the induced copies of any k<\/jats:italic>-node pattern H<\/jats:italic> in time $$2^{O(k^2)} O(n^{0.25k + 2} \\log n)$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n O<\/mml:mi>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 0.25<\/mml:mn>\n k<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if G<\/jats:italic> has bounded degeneracy, and in time $$2^{O(k^2)} O(n^{0.625k + 2} \\log n)$$<\/jats:tex-math>\n \n \n 2<\/mml:mn>\n \n O<\/mml:mi>\n (<\/mml:mo>\n \n k<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n O<\/mml:mi>\n \n (<\/mml:mo>\n \n n<\/mml:mi>\n \n 0.625<\/mml:mn>\n k<\/mml:mi>\n +<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n log<\/mml:mo>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> if G<\/jats:italic> has bounded average degree. These bounds are instantiations of a more general result, parameterized by the degeneracy of G<\/jats:italic> and the structure of H<\/jats:italic>, which generalizes classic bounds on counting cliques and complete bipartite graphs. We also give lower bounds based on the Exponential Time Hypothesis, showing that our results are actually a characterization of the complexity of subgraph counting in bounded-degeneracy graphs.<\/jats:p>","DOI":"10.1007\/s00453-021-00811-0","type":"journal-article","created":{"date-parts":[[2021,2,22]],"date-time":"2021-02-22T11:04:54Z","timestamp":1613991894000},"page":"2578-2605","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Faster algorithms for counting subgraphs in sparse graphs"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5211-2264","authenticated-orcid":false,"given":"Marco","family":"Bressan","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,2,22]]},"reference":[{"issue":"13","key":"811_CR1","doi-asserted-by":"publisher","first-page":"i241","DOI":"10.1093\/bioinformatics\/btn163","volume":"24","author":"N Alon","year":"2008","unstructured":"Alon, N., Dao, P., Hajirasouliha, I., Hormozdiari, F., Sahinalp, S.C.: Biomolecular network motif counting and discovery by color coding. Bioinformatics 24(13), i241-249 (2008)","journal-title":"Bioinformatics"},{"issue":"2","key":"811_CR2","first-page":"185","volume":"30","author":"D Berend","year":"2010","unstructured":"Berend, D., Tassa, T.: Improved bounds on Bell numbers and on moments of sums of random variables. Probab. Math. Stat. 30(2), 185\u2013205 (2010)","journal-title":"Probab. Math. Stat."},{"key":"811_CR3","doi-asserted-by":"crossref","unstructured":"Borgs, C., Chayes, J., Lov\u00e1sz, L., S\u00f3s, V.T., Vesztergombi, K.: Counting Graph Homomorphisms, pp. 315\u2013371 (2006)","DOI":"10.1007\/3-540-33700-8_18"},{"key":"811_CR4","unstructured":"Bressan, M.: Faster subgraph counting in sparse graphs. In: Proceedings of IPEC, vol. 148, pp. 6:1\u20136:15 (2019)"},{"key":"811_CR5","doi-asserted-by":"crossref","unstructured":"Bressan, M., Chierichetti, F., Kumar, R., Leucci, S., Panconesi, A.: Counting graphlets: space vs. time. In: Proceedings of ACM WSDM, pp. 557\u2013566 (2017)","DOI":"10.1145\/3018661.3018732"},{"issue":"2","key":"811_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3186586","volume":"20","author":"M Bressan","year":"2018","unstructured":"Bressan, M., Chierichetti, F., Kumar, R., Leucci, S., Panconesi, A.: Motif counting beyond five nodes. ACM Trans. Knowl. Discov. Data 20(2), 1\u201325 (2018)","journal-title":"ACM Trans. Knowl. Discov. Data"},{"issue":"11","key":"811_CR7","doi-asserted-by":"publisher","first-page":"1651","DOI":"10.14778\/3342263.3342640","volume":"12","author":"M Bressan","year":"2019","unstructured":"Bressan, M., Leucci, S., Panconesi, A.: Motivo: fast motif counting via succinct color coding and adaptive sampling. Proc. VLDB Endow. 12(11), 1651\u20131663 (2019)","journal-title":"Proc. VLDB Endow."},{"issue":"2","key":"811_CR8","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1016\/j.ic.2005.05.001","volume":"201","author":"J Chen","year":"2005","unstructured":"Chen, J., Chor, B., Fellows, M., Huang, X., Juedes, D., Kanj, I.A., Xia, G.: Tight lower bounds for certain parameterized NP-hard problems. Inf. Comput. 201(2), 216\u2013231 (2005)","journal-title":"Inf. Comput."},{"issue":"8","key":"811_CR9","doi-asserted-by":"publisher","first-page":"1346","DOI":"10.1016\/j.jcss.2006.04.007","volume":"72","author":"J Chen","year":"2006","unstructured":"Chen, J., Huang, X., Kanj, I.A., Xia, G.: Strong computational lower bounds via parameterized complexity. J. Comput. Syst. Sci. 72(8), 1346\u20131367 (2006)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"811_CR10","doi-asserted-by":"publisher","first-page":"210","DOI":"10.1137\/0214017","volume":"14","author":"N Chiba","year":"1985","unstructured":"Chiba, N., Nishizeki, T.: Arboricity and subgraph listing algorithms. SIAM J. Comput. 14(1), 210\u2013223 (1985)","journal-title":"SIAM J. Comput."},{"key":"811_CR11","doi-asserted-by":"crossref","unstructured":"Curticapean, R., Dell, H., Marx, D.: Homomorphisms are a good basis for counting small subgraphs. In: Proceedings of ACM STOC, pp. 210\u2013223 (2017)","DOI":"10.1145\/3055399.3055502"},{"key":"811_CR12","doi-asserted-by":"crossref","unstructured":"Curticapean, R., Marx, D.: Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts. In: Proceedings of IEEE FOCS, pp. 130\u2013139 (2014)","DOI":"10.1109\/FOCS.2014.22"},{"key":"811_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph Theory","author":"R Diestel","year":"2017","unstructured":"Diestel, R.: Graph Theory, 5th edn. Springer, Berlin (2017)","edition":"5"},{"issue":"4","key":"811_CR14","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0020-0190(94)90121-X","volume":"51","author":"D Eppstein","year":"1994","unstructured":"Eppstein, D.: Arboricity and bipartite subgraph listing algorithms. Inf. Process. Lett. 51(4), 207\u2013211 (1994)","journal-title":"Inf. Process. Lett."},{"issue":"3","key":"811_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.7155\/jgaa.00014","volume":"3","author":"D Eppstein","year":"1999","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. J. Graph Algorithms Appl. 3(3), 1\u201327 (1999)","journal-title":"J. Graph Algorithms Appl."},{"key":"811_CR16","doi-asserted-by":"crossref","unstructured":"Eppstein, D., L\u00f6ffler, M., Strash, D.: Listing all maximal cliques in sparse graphs in near-optimal time. In: Algorithms and Computation, pp. 403\u2013414. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-17517-6_36"},{"key":"811_CR17","doi-asserted-by":"crossref","unstructured":"Eppstein, David, Strash, Darren: Listing all maximal cliques in large sparse real-world graphs. In: Experimental Algorithms, pp. 364\u2013375. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-20662-7_31"},{"key":"811_CR18","doi-asserted-by":"crossref","unstructured":"Fedor, V.: Fomin and Dieter Kratsch, 1st edn. Exact Exponential Algorithms. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-16533-7_1"},{"key":"811_CR19","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1016\/j.jctb.2015.09.001","volume":"116","author":"R Ganian","year":"2016","unstructured":"Ganian, R., Hlin\u011bn\u00fd, P., Kneis, J., Meister, D., Obdr\u017e\u00e1lek, J., Rossmanith, P., Sikdar, S.: Are there any good digraph width measures? J. Comb. Theory Ser. B 116, 250\u2013286 (2016)","journal-title":"J. Comb. Theory Ser. B"},{"key":"811_CR20","first-page":"21","volume":"24","author":"M Grohe","year":"2013","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Characterisations of nowhere dense graphs (invited talk). Proc. FSTTCS 24, 21\u201340 (2013)","journal-title":"Proc. FSTTCS"},{"issue":"1","key":"811_CR21","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.jctb.2008.06.004","volume":"99","author":"M Grohe","year":"2009","unstructured":"Grohe, M., Marx, D.: On tree width, bramble size, and expansion. J. Comb. Theory Ser. B 99(1), 218\u2013228 (2009)","journal-title":"J. Comb. Theory Ser. B"},{"key":"811_CR22","doi-asserted-by":"crossref","unstructured":"Grohe, M., Schweikardt, N.: First-order query evaluation with cardinality conditions. In: Proceedings of ACM SIGMOD, pp. 253\u2013266 (2018)","DOI":"10.1145\/3196959.3196970"},{"key":"811_CR23","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? In: Proceedings of IEEE FOCS, pp. 653\u2013662 (1998)"},{"key":"811_CR24","doi-asserted-by":"crossref","unstructured":"Kneis, J., M\u00f6lle, D., Richter, S., Rossmanith, P.: Algorithms based on the treewidth of sparse graphs. In: Graph-Theoretic Concepts in Computer Science, pp. 385\u2013396. Springer, Berlin (2005)","DOI":"10.1007\/11604686_34"},{"key":"811_CR25","doi-asserted-by":"crossref","unstructured":"Le\u00a0Gall, F.: Powers of tensors and fast matrix multiplication. In: Proceedings of ISSAC, pp. 296\u2013303 (2014)","DOI":"10.1145\/2608628.2608664"},{"issue":"3","key":"811_CR26","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/0020-0190(79)90004-8","volume":"8","author":"R Mathon","year":"1979","unstructured":"Mathon, R.: A note on the graph isomorphism counting problem. Inf. Process. Lett. 8(3), 131\u2013136 (1979)","journal-title":"Inf. Process. Lett."},{"key":"811_CR27","doi-asserted-by":"crossref","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: Sparsity: graphs, structures, and algorithms. In: Algorithms and Combinatorics. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"issue":"4","key":"811_CR28","doi-asserted-by":"publisher","first-page":"600","DOI":"10.1016\/j.ejc.2011.01.006","volume":"32","author":"J Ne\u0161et\u0159il","year":"2011","unstructured":"Ne\u0161et\u0159il, J., de Mendez, P.O.: On nowhere dense graphs. Eur. J. Combin. 32(4), 600\u2013617 (2011)","journal-title":"Eur. J. Combin."},{"issue":"2","key":"811_CR29","first-page":"415","volume":"026","author":"J Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carol. 026(2), 415\u2013419 (1985)","journal-title":"Comment. Math. Univ. Carol."},{"issue":"5","key":"811_CR30","doi-asserted-by":"publisher","first-page":"1844","DOI":"10.1007\/s00453-018-0511-9","volume":"81","author":"V Patel","year":"2018","unstructured":"Patel, V., Regts, G.: Computing the number of induced copies of a fixed graph in a bounded degree graph. Algorithmica 81(5), 1844\u20131858 (2018)","journal-title":"Algorithmica"},{"key":"811_CR31","doi-asserted-by":"crossref","unstructured":"Sariy\u00fcce, A.E., Pinar, A.: Peeling bipartite networks for dense subgraph discovery. In: Proceedings of ACM WSDM, pp. 504\u2013512 (2018)","DOI":"10.1145\/3159652.3159678"},{"issue":"3","key":"811_CR32","doi-asserted-by":"publisher","first-page":"16:1","DOI":"10.1145\/3057742","volume":"11","author":"AE Sariy\u00fcce","year":"2017","unstructured":"Sariy\u00fcce, A.E., Seshadhri, C., Pinar, A., \u00c7ataly\u00fcrek, \u00dc.V.: Nucleus decompositions for identifying hierarchy of dense subgraphs. ACM Trans. Web 11(3), 16:1-16:27 (2017)","journal-title":"ACM Trans. Web"},{"key":"811_CR33","doi-asserted-by":"crossref","unstructured":"Tsourakakis, C.E., Pachocki, J., Mitzenmacher, M.: Scalable motif-aware graph clustering. In: Proceedings of WWW, pp. 1451\u20131460 (2017)","DOI":"10.1145\/3038912.3052653"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00811-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00811-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00811-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T14:03:08Z","timestamp":1626962588000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00811-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,22]]},"references-count":33,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["811"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00811-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,22]]},"assertion":[{"value":"6 January 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 February 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}