{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T05:13:54Z","timestamp":1790745234072,"version":"4.1.0"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","funder":[{"DOI":"10.13039\/501100004281","name":"Polish National Science Centre","doi-asserted-by":"crossref","award":["2018\/31\/D\/ST6\/00062"],"award-info":[{"award-number":["2018\/31\/D\/ST6\/00062"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100010663","name":"H2020 European Research Council","doi-asserted-by":"publisher","award":["714704"],"award-info":[{"award-number":["714704"]}],"id":[{"id":"10.13039\/100010663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>For a fixed graph $H$, by Hom($H$) we denote the computational problem which asks whether a given graph $G$ admits a homomorphism to $H$, i.e., an edge-preserving mapping from $V(G)$ to $V(H)$. As Hom($K_k$) is equivalent to $k$-Coloring, graph homomorphisms can be seen as generalizations of colorings. It is known that Hom($H$) is polynomial-time solvable if $H$ is bipartite or has a vertex with a loop, and NP-complete otherwise [Hell and Ne\u0161et\u0159il, J. Comb. Theory Ser. B, 48 (1990), pp. 92--110]. In this paper we are interested in the complexity of the problem, parameterized by the treewidth of the input graph $G$. If $G$ has $n$ vertices and is given along with its tree decomposition of width ${tw}(G)$, then the problem can be solved in time $|V(H)|^{{tw}(G)} \\cdot n^{\\mathcal{O}(1)}$, using a straightforward dynamic programming. We explore whether this bound can be improved. We show that if $H$ is a projective core, then the existence of such a faster algorithm is unlikely: assuming the Strong Exponential Time Hypothesis, the Hom($H$) problem cannot be solved in time $(|V(H)|-\\epsilon)^{{tw}(G)} \\cdot n^{\\mathcal{O}(1)}$, for any $\\epsilon &gt; 0$. This result provides a full complexity characterization for a large class of graphs $H$, as almost all graphs are projective cores. We also notice that the naive algorithm can be improved for some graphs $H$ and show a complexity classification for all graphs $H$, assuming two conjectures from algebraic graph theory. In particular, there are no known graphs $H$ which are not covered by our result.<\/jats:p>","DOI":"10.1137\/20m1320146","type":"journal-article","created":{"date-parts":[[2021,4,1]],"date-time":"2021-04-01T11:22:07Z","timestamp":1617276127000},"page":"487-508","source":"Crossref","is-referenced-by-count":12,"title":["Fine-Grained Complexity of the Graph Homomorphism Problem for Bounded-Treewidth Graphs"],"prefix":"10.1137","volume":"50","author":[{"given":"Karolina","family":"Okrasa","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":true,"given":"Pawe\u0142","family":"Rza\u0345\u017cewski","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,4,1]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1137\/0608024"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"atypb3","unstructured":"U. Bertele and F. Brioschi,\n                      Nonserial Dynamic Programming\n                      , Academic Press, 1972."},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1137\/070683933"},{"key":"atypb5","first-page":"41","author":"Bodlaender H. L.","year":"2013","journal-title":"New York"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2014.12.008"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxm037"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2012.07.018"},{"key":"atypb9","first-page":"40","volume":"32","author":"Brinkmann G.","year":"1997","journal-title":"Graph Theory Notes of New York"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.028"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1145\/3051094"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. Cygan, F. V. Fomin, \u0141. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh,\n                      Parameterized algorithms\n                      , Springer, New York, 2015.","DOI":"10.1007\/978-3-319-21275-3"},{"key":"atypb14","first-page":"15","volume":"9","author":"D\u00f6rfler W.","year":"1974","journal-title":"Glasnik Matemati\u010dki"},{"key":"atypb15","unstructured":"L. Egri, D. Marx, and P. Rza\u0345\u017cewski,\n                      Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: a complete complexity characterization\n                      , in Proceedings of the 35th Symposium on Theoretical Aspects of Computer Science, STACS 2018, February 28 to March 3, 2018, Caen, France, R. Niedermeier and B. Vall\u00e9e, eds., vol. 96 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018, pp. 27:1-27:15,https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2018.27."},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1959-003-9"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10073"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-007-2007-x"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1007\/BF01886093"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1007\/BF01917434"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.26493\/1855-3974.114.4bb"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"R. H. Hammack, W. Imrich, and S. Klav\u017ear,\n                      Handbook of product graphs\n                      , CRC Press, 2011.","DOI":"10.1201\/b10959"},{"key":"atypb25","unstructured":"S. T. Hedetniemi,\n                      Homomorphisms of graphs and automata\n                      , tech. report, 1966."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90282-K"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"P. Hell and J. Ne\u0161et\u0159il,\n                      Graphs and homomorphisms\n                      , Oxford University Press, 2004.","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00592-7"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1175"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-2002-029-7"},{"key":"atypb34","first-page":"339","volume":"7","author":"Larose B.","year":"2001","journal-title":"Multiple-Valued Logic"},{"key":"atypb35","first-page":"41","volume":"105","author":"Lokshtanov D.","year":"2011","journal-title":"Bull. EATCS"},{"key":"atypb36","first-page":"1","volume":"14","author":"Lokshtanov D.","year":"2018","journal-title":"ACM Trans. Algorithms"},{"key":"atypb37","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20017"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.4064\/fm-70-1-59-101"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.4153\/CJM-1968-151-x"},{"key":"atypb40","unstructured":"K. Okrasa, M. Piecyk, and P. Rza\u0345\u017cewski,\n                      Full complexity classification of the list homomorphism problem for bounded-treewidth graphs\n                      , in Proceedings of the 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), F. Grandoni, G. Herman, and P. Sanders, eds., vol. 173 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 2020, pp. 74:1-74:24,https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2020.74."},{"key":"atypb41","first-page":"520","author":"Pilipczuk M.","year":"2011","journal-title":"New York"},{"key":"atypb42","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"atypb43","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2014.02.012"},{"key":"atypb44","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00213-2"},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2019.190.2.6"},{"key":"atypb46","doi-asserted-by":"publisher","DOI":"10.1137\/080736697"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1093\/qmath\/22.4.551"},{"key":"atypb48","first-page":"2","volume":"54","author":"Tardif C.","year":"2008","journal-title":"Graph Theory Notes NY"},{"key":"atypb49","doi-asserted-by":"crossref","unstructured":"J. M. M. van Rooij, H. L. Bodlaender, and P. Rossmanith,\n                      Dynamic programming on tree decompositions using generalised fast subset convolution\n                      , in Proceedings of the Algorithms - ESA 2009, 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009. Proceedings, A. Fiat and P. Sanders, eds., vol. 5757 of Lecture Notes in Computer Science, Springer, 2009, pp. 566-577,https:\/\/doi.org\/10.1007\/978-3-642-04128-0_51.","DOI":"10.1007\/978-3-642-04128-0_51"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9261-z"},{"key":"atypb51","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1962-0133816-6"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1320146","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:29Z","timestamp":1787339969000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1320146"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":51,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1320146"],"URL":"https:\/\/doi.org\/10.1137\/20m1320146","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}