{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:57:18Z","timestamp":1750309038114,"version":"3.41.0"},"reference-count":42,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","license":[{"start":{"date-parts":[[2023,12,12]],"date-time":"2023-12-12T00:00:00Z","timestamp":1702339200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NWO"},{"name":"European Research Council"},{"name":"European Union\u2019s Horizon 2020","award":["714704"],"award-info":[{"award-number":["714704"]}]},{"name":"DFG Emmy Noether","award":["KR 4286\/1"],"award-info":[{"award-number":["KR 4286\/1"]}]},{"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. Comput. Theory"],"published-print":{"date-parts":[[2023,12,31]]},"abstract":"<jats:p>\n            We investigate the\n            <jats:sc>\n              List\n              <jats:italic>H<\/jats:italic>\n              -Coloring\n            <\/jats:sc>\n            problem, the generalization of graph coloring that asks whether an input graph\u00a0\n            <jats:italic>G<\/jats:italic>\n            admits a homomorphism to the undirected graph\u00a0\n            <jats:italic>H<\/jats:italic>\n            (possibly with loops), such that each vertex\u00a0\n            <jats:italic>v<\/jats:italic>\n            \u2208\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>G<\/jats:italic>\n            ) is mapped to a vertex on its list\u00a0\n            <jats:italic>L<\/jats:italic>\n            (\n            <jats:italic>v<\/jats:italic>\n            ) \u2286\n            <jats:italic>V<\/jats:italic>\n            (\n            <jats:italic>H<\/jats:italic>\n            ). An important result by Feder, Hell, and Huang [JGT\u00a02003] states that\n            <jats:sc>\n              List\n              <jats:italic>H<\/jats:italic>\n              -Coloring\n            <\/jats:sc>\n            is polynomial-time solvable if\u00a0\n            <jats:italic>H<\/jats:italic>\n            is a so-called\n            <jats:italic>bi-arc graph<\/jats:italic>\n            , and NP-complete otherwise. We investigate the NP-complete cases of the problem from the perspective of polynomial-time sparsification: can an\n            <jats:italic>n<\/jats:italic>\n            -vertex instance be efficiently reduced to an equivalent instance of bitsize\u00a0\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathcal {O} (n^{2-\\varepsilon })\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2-\u025b<\/jats:sup>\n            ) for some\u00a0\u025b &gt; 0? We prove that if\u00a0\n            <jats:italic>H<\/jats:italic>\n            is not a bi-arc graph, then\n            <jats:sc>\n              List\n              <jats:italic>H<\/jats:italic>\n              -Coloring\n            <\/jats:sc>\n            does not admit such a sparsification algorithm unless\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {NP \\subseteq coNP\/poly}\\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            . Our proofs combine techniques from kernelization lower bounds with a study of the structure of graphs\u00a0\n            <jats:italic>H<\/jats:italic>\n            which are not bi-graphs.\n          <\/jats:p>","DOI":"10.1145\/3612938","type":"journal-article","created":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T12:01:37Z","timestamp":1694779297000},"page":"1-23","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Sparsification Lower Bounds for List\n            <i>H<\/i>\n            -Coloring"],"prefix":"10.1145","volume":"15","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-4025-8086","authenticated-orcid":false,"given":"Hubie","family":"Chen","sequence":"first","affiliation":[{"name":"King\u2019s College London, United Kingdom"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8204-1268","authenticated-orcid":false,"given":"Bart M. P.","family":"Jansen","sequence":"additional","affiliation":[{"name":"Eindhoven University of Technology, The Netherlands"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1414-3507","authenticated-orcid":false,"given":"Karolina","family":"Okrasa","sequence":"additional","affiliation":[{"name":"University of Warsaw, Institute of Informatics, Poland and Warsaw University of Technology, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3721-6721","authenticated-orcid":false,"given":"Astrid","family":"Pieterse","sequence":"additional","affiliation":[{"name":"Humboldt-Universit\u00e4t zu Berlin, 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, Poland and University of Warsaw, Institute of Informatics, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,12,12]]},"reference":[{"key":"e_1_3_1_2_2","first-page":"19","article-title":"Homomorphisms of 3-chromatic graphs. II","volume":"47","author":"Albertson Michael O.","year":"1985","unstructured":"Michael O. Albertson, Paul A. Catlin, and Luana Gibbons. 1985. Homomorphisms of 3-chromatic graphs. II, Congr. Numer. 47, 19\u201328.","journal-title":"Congr. Numer."},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v34i02.5499"},{"key":"e_1_3_1_4_2","doi-asserted-by":"publisher","DOI":"10.1137\/120880240"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.028"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CP.2022.11"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2020.58"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2018.15"},{"key":"e_1_3_1_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2015.52"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2629620"},{"key":"e_1_3_1_11_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.26"},{"key":"e_1_3_1_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-011-9333-8"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2018.27"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21659"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1997.1812"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s004939970003"},{"key":"e_1_3_1_17_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10073"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.09.030"},{"key":"e_1_3_1_19_2","doi-asserted-by":"publisher","DOI":"10.1017\/9781107415157"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(00)00009-1"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.04.010"},{"key":"e_1_3_1_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/1233481.1233493"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8937-6_4"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90132-J"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198528173.001.0001"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(83)90020-3"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57586-5_29"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-014-9924-2"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.IPEC.2017.22"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-016-0189-9"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00578-5"},{"key":"e_1_3_1_32_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2015.07.011"},{"key":"e_1_3_1_33_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-66158-2_11"},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.05.016"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(81)90226-6"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-10856-4_76"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ESA.2020.74"},{"key":"e_1_3_1_38_2","article-title":"Full complexity classification of the list homomorphism problem for bounded-treewidth graphs","volume":"2006","author":"Okrasa Karolina","year":"2020","unstructured":"Karolina Okrasa, Marta Piecyk, and Pawe\u0142 Rz\u0105a\u017cewski. 2020. Full complexity classification of the list homomorphism problem for bounded-treewidth graphs. CoRR abs\/2006.11155 (2020). arxiv:2006.11155https:\/\/arxiv.org\/abs\/2006.11155.","journal-title":"CoRR"},{"key":"e_1_3_1_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.97"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.12.004"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/080736697"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.02.003"},{"key":"e_1_3_1_43_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(76)80011-8"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3612938","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3612938","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T22:29:18Z","timestamp":1750285758000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3612938"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,12]]},"references-count":42,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2023,12,31]]}},"alternative-id":["10.1145\/3612938"],"URL":"https:\/\/doi.org\/10.1145\/3612938","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2023,12,12]]},"assertion":[{"value":"2020-12-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-05-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}