{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:53Z","timestamp":1740109313506,"version":"3.37.3"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:00:00Z","timestamp":1614643200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T00:00:00Z","timestamp":1614643200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["PGS D"],"award-info":[{"award-number":["PGS D"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,8]]},"DOI":"10.1007\/s00453-021-00813-y","type":"journal-article","created":{"date-parts":[[2021,3,2]],"date-time":"2021-03-02T11:05:58Z","timestamp":1614683158000},"page":"2521-2551","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Beating Treewidth for Average-Case Subgraph Isomorphism"],"prefix":"10.1007","volume":"83","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5099-9882","authenticated-orcid":false,"given":"Gregory","family":"Rosenthal","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,3,2]]},"reference":[{"issue":"2","key":"813_CR1","doi-asserted-by":"publisher","first-page":"631","DOI":"10.1137\/100812653","volume":"25","author":"N Alon","year":"2011","unstructured":"Alon, N., Marx, D.: Sparse balanced partitions and the complexity of subgraph problems. SIAM J. Discrete Math. 25(2), 631\u2013644 (2011). https:\/\/doi.org\/10.1137\/100812653","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"813_CR2","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1016\/0095-8956(85)90092-9","volume":"38","author":"N Alon","year":"1985","unstructured":"Alon, N., Milman, V.D.: $$\\lambda _1,$$ isoperimetric inequalities for graphs, and superconcentrators. J. Combin. Theory Ser. B 38(1), 73\u201388 (1985). https:\/\/doi.org\/10.1016\/0095-8956(85)90092-9","journal-title":"J. Combin. Theory Ser. B"},{"issue":"4","key":"813_CR3","doi-asserted-by":"publisher","first-page":"844","DOI":"10.1145\/210332.210337","volume":"42","author":"N Alon","year":"1995","unstructured":"Alon, N., Yuster, R., Zwick, U.: Color-coding. J. ACM 42(4), 844\u2013856 (1995). https:\/\/doi.org\/10.1145\/210332.210337","journal-title":"J. ACM"},{"issue":"2","key":"813_CR4","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1007\/s00037-010-0288-y","volume":"19","author":"K Amano","year":"2010","unstructured":"Amano, K.: $$k$$-subgraph isomorphism on $${{\\rm AC}}^0$$ circuits. Comput. Complex. 19(2), 183\u2013210 (2010). https:\/\/doi.org\/10.1007\/s00037-010-0288-y","journal-title":"Comput. Complex."},{"issue":"1\u20132","key":"813_CR5","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"HL Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial $$k$$-arboretum of graphs with bounded treewidth. Theoret. Comput. Sci. 209(1\u20132), 1\u201345 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00228-4","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"813_CR6","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1093\/comjnl\/bxm037","volume":"51","author":"HL Bodlaender","year":"2008","unstructured":"Bodlaender, H.L., Koster, A.M.C.A.: Combinatorial optimization on graphs of bounded treewidth. Comput. J. 51(3), 255\u2013269 (2008). https:\/\/doi.org\/10.1093\/comjnl\/bxm037","journal-title":"Comput. J."},{"issue":"3","key":"813_CR7","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/j.disc.2005.12.011","volume":"306","author":"LS Chandran","year":"2006","unstructured":"Chandran, L.S., Kavitha, T.: The treewidth and pathwidth of hypercubes. Discrete Math. 306(3), 359\u2013365 (2006). https:\/\/doi.org\/10.1016\/j.disc.2005.12.011","journal-title":"Discrete Math."},{"issue":"1\u20133","key":"813_CR8","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1016\/j.tcs.2004.05.009","volume":"326","author":"F Eisenbrand","year":"2004","unstructured":"Eisenbrand, F., Grandoni, F.: On the complexity of fixed parameter clique and dominating set. Theoret. Comput. Sci. 326(1\u20133), 57\u201367 (2004). https:\/\/doi.org\/10.1016\/j.tcs.2004.05.009","journal-title":"Theoret. Comput. Sci."},{"issue":"1\u20133","key":"813_CR9","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1016\/S0166-218X(99)00082-7","volume":"95","author":"LH Harper","year":"1999","unstructured":"Harper, L.H.: On an isoperimetric problem for Hamming graphs. Discrete Appl. Math. 95(1\u20133), 285\u2013309 (1999). https:\/\/doi.org\/10.1016\/S0166-218X(99)00082-7","journal-title":"Discrete Appl. Math."},{"key":"813_CR10","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511616679","volume-title":"Global Methods for Combinatorial Isoperimetric Problems, Cambridge Studies in Advanced Mathematics","author":"LH Harper","year":"2004","unstructured":"Harper, L.H.: Global Methods for Combinatorial Isoperimetric Problems, Cambridge Studies in Advanced Mathematics, vol. 90. Cambridge University Press, Cambridge (2004). https:\/\/doi.org\/10.1017\/CBO9780511616679"},{"issue":"4","key":"813_CR11","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1002\/jgt.22030","volume":"84","author":"DJ Harvey","year":"2017","unstructured":"Harvey, D.J., Wood, D.R.: Parameters tied to treewidth. J. Graph Theory 84(4), 364\u2013385 (2017). https:\/\/doi.org\/10.1137\/1008126530","journal-title":"J. Graph Theory"},{"key":"813_CR12","doi-asserted-by":"publisher","unstructured":"H\u00e5stad, J.: Almost optimal lower bounds for small depth circuits. In: Proceedings of the 18th annual ACM Symposium on Theory of Computing (STOC), pp. 6\u201320 (1986). https:\/\/doi.org\/10.1145\/12130.12132","DOI":"10.1145\/12130.12132"},{"issue":"2","key":"813_CR13","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1006\/inco.1994.1008","volume":"108","author":"J H\u00e5stad","year":"1994","unstructured":"H\u00e5stad, J., Wegener, I., Wurm, N., Yi, S.Z.: Optimal depth, very small size circuits for symmetric functions in $${{\\rm AC}}^0$$. Inform. Comput. 108(2), 200\u2013211 (1994). https:\/\/doi.org\/10.1006\/inco.1994.1008","journal-title":"Inform. Comput."},{"issue":"4","key":"813_CR14","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-06-01126-8","volume":"43","author":"S Hoory","year":"2006","unstructured":"Hoory, S., Linial, N., Wigderson, A.: Expander graphs and their applications. Bull. Am. Math. Soc. (N.S.) 43(4), 439\u2013561 (2006). https:\/\/doi.org\/10.1090\/S0273-0979-06-01126-8","journal-title":"Bull. Am. Math. Soc. (N.S.)"},{"issue":"4","key":"813_CR15","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"813_CR16","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1002\/rsa.3240010209","volume":"1","author":"S Janson","year":"1990","unstructured":"Janson, S.: Poisson approximation for large deviations. Random Struct. Algorithms 1(2), 221\u2013229 (1990). https:\/\/doi.org\/10.1002\/rsa.3240010209","journal-title":"Random Struct. Algorithms"},{"issue":"3","key":"813_CR17","doi-asserted-by":"publisher","first-page":"936","DOI":"10.1137\/14099721X","volume":"46","author":"Y Li","year":"2017","unstructured":"Li, Y., Razborov, A., Rossman, B.: On the $${{\\rm AC}}^0$$ complexity of subgraph isomorphism. SIAM J. Comput. 46(3), 936\u2013971 (2017). https:\/\/doi.org\/10.1137\/1008126534","journal-title":"SIAM J. Comput."},{"issue":"1","key":"813_CR18","doi-asserted-by":"publisher","first-page":"85","DOI":"10.4086\/toc.2010.v006a005","volume":"6","author":"D Marx","year":"2010","unstructured":"Marx, D.: Can you beat treewidth? Theory Comput. 6(1), 85\u2013112 (2010). https:\/\/doi.org\/10.1137\/1008126535","journal-title":"Theory Comput."},{"key":"813_CR19","doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M.: Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask). In: Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS), vol.\u00a025, pp. 542\u2013553 (2014). https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2014.542","DOI":"10.4230\/LIPIcs.STACS.2014.542"},{"issue":"2","key":"813_CR20","first-page":"415","volume":"26","author":"J Ne\u0161et\u0159il","year":"1985","unstructured":"Ne\u0161et\u0159il, J., Poljak, S.: On the complexity of the subgraph problem. Comment. Math. Univ. Carolin. 26(2), 415\u2013419 (1985)","journal-title":"Comment. Math. Univ. Carolin."},{"issue":"3","key":"813_CR21","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986). https:\/\/doi.org\/10.1016\/0196-6774(86)90023-4","journal-title":"J. Algorithms"},{"key":"813_CR22","doi-asserted-by":"publisher","unstructured":"Rossman, B.: On the constant-depth complexity of $$k$$-clique. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing (STOC), pp. 721\u2013730 (2008). https:\/\/doi.org\/10.1145\/1374376.1374480","DOI":"10.1145\/1374376.1374480"},{"issue":"1","key":"813_CR23","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1137\/110839059","volume":"43","author":"B Rossman","year":"2014","unstructured":"Rossman, B.: The monotone complexity of $$k$$-clique on random graphs. SIAM J. Comput. 43(1), 256\u2013279 (2014). https:\/\/doi.org\/10.1137\/1008126536","journal-title":"SIAM J. Comput."},{"key":"813_CR24","doi-asserted-by":"publisher","first-page":"3409","DOI":"10.1142\/9789813272880_0187","volume":"3","author":"B Rossman","year":"2018","unstructured":"Rossman, B.: Lower bounds for subgraph isomorphism. Proc. Int. Cong. Math. (ICM) 3, 3409\u20133430 (2018). https:\/\/doi.org\/10.1142\/9789813272880_0187","journal-title":"Proc. Int. Cong. Math. (ICM)"},{"key":"813_CR25","volume-title":"Database System Concepts","author":"A Silberschatz","year":"2011","unstructured":"Silberschatz, A., Korth, H.F., Sudarshan, S.: Database System Concepts, 6th edn. McGraw-Hill, London (2011)","edition":"6"},{"key":"813_CR26","doi-asserted-by":"crossref","unstructured":"Yao, A.C.C.: Probabilistic computations: toward a unified measure of complexity. In: Proceedings of the 18th Annual IEEE Symposium on Foundations of Computer Science, pp. 222\u2013227 (1977)","DOI":"10.1109\/SFCS.1977.24"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00813-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-021-00813-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-021-00813-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,7,22]],"date-time":"2021-07-22T14:03:39Z","timestamp":1626962619000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-021-00813-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,2]]},"references-count":26,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,8]]}},"alternative-id":["813"],"URL":"https:\/\/doi.org\/10.1007\/s00453-021-00813-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2021,3,2]]},"assertion":[{"value":"18 December 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 February 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with Ethical Standards"}},{"value":"Benjamin Rossman, one of the coauthors of Li et. al. [], has been the author\u2019s MSc and PhD supervisor throughout the writing of this paper. The author has also received funding from Dr. Rossman, including for the purpose of presenting this paper at IPEC 2019.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}