{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T07:21:46Z","timestamp":1760080906807,"version":"3.41.0"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2024,2,13]],"date-time":"2024-02-13T00:00:00Z","timestamp":1707782400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"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"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"\n The goal of this work is to give precise bounds on the counting complexity of a family of generalized coloring problems (list homomorphisms) on bounded-treewidth graphs. Given graphs\n G<\/jats:italic>\n ,\n H<\/jats:italic>\n , and lists\n L (v)<\/jats:italic>\n \u2286\n V(H)<\/jats:italic>\n for every\n v<\/jats:italic>\n \u2208\n V(G)<\/jats:italic>\n , a\n f:V(G)<\/jats:italic>\n \u2192\n V(H)<\/jats:italic>\n that preserves the edges (i.e.,\n uv<\/jats:italic>\n \u2208\n E(G)<\/jats:italic>\n implies\n f(u)f(v)<\/jats:italic>\n \u2208\n E(H)<\/jats:italic>\n ) and respects the lists (i.e.,\n f(v)<\/jats:italic>\n \u2208\n L(v)<\/jats:italic>\n ). Standard techniques show that if\n G<\/jats:italic>\n is given with a tree decomposition of width\n t<\/jats:italic>\n , then the number of list homomorphisms can be counted in time\n |V(H)|<\/jats:italic>\n \n t<\/jats:italic>\n <\/jats:sup>\n \u22c5\n n<\/jats:italic>\n \ud835\udcaa(1)<\/jats:sup>\n . Our main result is determining, for every fixed graph\n H<\/jats:italic>\n , how much the base\n |V(H)|<\/jats:italic>\n in the running time can be improved. For a connected graph\n H<\/jats:italic>\n , we define irr(\n H<\/jats:italic>\n ) in the following way: if\n H<\/jats:italic>\n has a loop or is nonbipartite, then irr(\n H<\/jats:italic>\n ) is the maximum size of a set\n S\u2286 V(H)<\/jats:italic>\n where any two vertices have different neighborhoods; if\n H<\/jats:italic>\n is bipartite, then irr(\n H<\/jats:italic>\n ) is the maximum size of such a set that is fully in one of the bipartition classes. For disconnected\n H<\/jats:italic>\n , we define irr(\n H<\/jats:italic>\n ) as the maximum of irr(\n C<\/jats:italic>\n ) over every connected component\n C<\/jats:italic>\n of\n H<\/jats:italic>\n . It follows from earlier results that if irr(\n H<\/jats:italic>\n )=1, then the problem of counting list homomorphisms to\n H<\/jats:italic>\n is polynomial-time solvable, and otherwise it is #P-hard. We show that, for every fixed graph\n H<\/jats:italic>\n , the number of list homomorphisms from\n (G,L)<\/jats:italic>\n to\n H<\/jats:italic>\n \n \n \u2014<\/jats:label>\n \n can be counted in time\n \n \\(\\operatorname{irr}(H)^t\\cdot n^{\\mathcal {O}(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n if a tree decomposition of\n G<\/jats:italic>\n having width at most\n t<\/jats:italic>\n is given in the input, and,\n <\/jats:p>\n <\/jats:list-item>\n \n \u2014<\/jats:label>\n \n given that\n \n \\(\\operatorname{irr}(H)\\ge 2\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , cannot be counted in time\n \n \\((\\operatorname{irr}(H)-\\varepsilon)^t\\cdot n^{\\mathcal {O}(1)}\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for any\n \n \\(\\varepsilon \\gt 0\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , even if a tree decomposition of\n G<\/jats:italic>\n having width at most\n t<\/jats:italic>\n is given in the input, unless the Counting Strong Exponential-Time Hypothesis (#SETH) fails.\n <\/jats:p>\n <\/jats:list-item>\n <\/jats:list>\n Thereby, we give a precise and complete complexity classification featuring matching upper and lower bounds for all target graphs with or without loops.\n <\/jats:p>","DOI":"10.1145\/3640814","type":"journal-article","created":{"date-parts":[[2024,1,16]],"date-time":"2024-01-16T12:02:07Z","timestamp":1705406527000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds"],"prefix":"10.1145","volume":"20","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6895-755X","authenticated-orcid":false,"given":"Jacob","family":"Focke","sequence":"first","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarb\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5686-8314","authenticated-orcid":false,"given":"D\u00e1niel","family":"Marx","sequence":"additional","affiliation":[{"name":"CISPA Helmholtz Center for Information Security, Saarb\u00fccken, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7696-3848","authenticated-orcid":false,"given":"Pawe\u0142","family":"Rz\u0105\u017cewski","sequence":"additional","affiliation":[{"name":"Warsaw University of Technology, Faculty of Mathematics and Information Science, Warsaw, Poland and Warsaw, Institute of Informatics, Warsaw, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,2,13]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2011.25"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","unstructured":"Glencora Borradaile and Hung Le. 2016. Optimal dynamic program for r-domination problems over tree decompositions. In 11th International Symposium on Parameterized and Exact Computation Jiong Guo and Danny Hermelin (Eds.). Leibniz International Proceedings in Informatics Vol. 63. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik Article 8 23 pages. DOI:10.4230\/LIPIcs.IPEC.2016.8","DOI":"10.4230\/LIPIcs.IPEC.2016.8"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.028"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1145\/1970398.1970400"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2015.07.004"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.70"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch113"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/2635812"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","unstructured":"Josep D\u00edaz Maria J. Serna and Dimitrios M. Thilikos. 2001. Recent results on parameterized H-colorings. In Graphs Morphisms and Statistical Physics Jaroslav Ne\u0161et\u0159il and Peter Winkler (Eds.). DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 63. DIMACS\/AMS 65\u201385. DOI:10.1090\/dimacs\/063\/05","DOI":"10.1090\/dimacs\/063\/05"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00017-8"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1002\/1098-2418(200010\/12)17:3\/4<260::AID-RSA5>3.0.CO;2-W"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","unstructured":"L\u00e1szl\u00f3 Egri D\u00e1niel Marx and Pawe\u0142 Rz\u0105\u017cewski. 2018. Finding list homomorphisms from bounded-treewidth graphs to reflexive graphs: A complete complexity characterization. In 35th Symposium on Theoretical Aspects of Computer Science Rolf Niedermeier and Brigitte Vall\u00e9e (Eds.). Leibniz International Proceedings in Informatics Vol. 96. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik Article 27 15 pages. DOI:10.4230\/LIPIcs.STACS.2018.27","DOI":"10.4230\/LIPIcs.STACS.2018.27"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10073"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794266766"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8937-6_4"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","unstructured":"Pavol Hell and Jaroslav Ne\u0161et\u0159il. 2001. Counting list homomorphisms and graphs with bounded degrees. In Graphs Morphisms and Statistical Physics Jaroslav Ne\u0161et\u0159il and Peter Winkler (Eds.). DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 63. DIMACS\/AMS 105\u2013112. DOI:10.1090\/dimacs\/063\/08","DOI":"10.1090\/dimacs\/063\/08"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2008.10.003"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2020.100352"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2018.11.002"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1137\/19M1280326"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3170442"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","unstructured":"D\u00e1niel Marx Govind S. Sankar and Philipp Schepper. 2021. Degrees and gaps: Tight complexity results of general factor problems parameterized by treewidth and cutwidth. In 48th International Colloquium on Automata Languages and Programming Nikhil Bansal Emanuela Merelli and James Worrell (Eds.). Leibniz International Proceedings in Informatics Vol. 198. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik Article 95 20 pages. DOI:10.4230\/LIPIcs.ICALP.2021.95","DOI":"10.4230\/LIPIcs.ICALP.2021.95"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(81)90037-8"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(81)90226-6"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","unstructured":"Karolina Okrasa Marta Piecyk and Pawe\u0142 Rz\u0105\u017cewski. 2020. Full complexity classification of the list homomorphism problem for bounded-treewidth graphs. In 28th Annual European Symposium on Algorithms Fabrizio Grandoni Grzegorz Herman and Peter Sanders (Eds.). Leibniz International Proceedings in Informatics Vol. 173. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik Article 74 24 pages. DOI:10.4230\/LIPIcs.ESA.2020.74","DOI":"10.4230\/LIPIcs.ESA.2020.74"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M1320146"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1137\/080736697"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3640814","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3640814","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:57:56Z","timestamp":1750294676000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3640814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,2,13]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3640814"],"URL":"https:\/\/doi.org\/10.1145\/3640814","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2024,2,13]]},"assertion":[{"value":"2022-01-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-11-14","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-02-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}