{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:20:46Z","timestamp":1750220446719,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1714275"],"award-info":[{"award-number":["CCF-1714275"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            Graph homomorphism has been an important research topic since its introduction\u00a0[20]. Stated in the language of binary relational structures in that paper\u00a0[20], Lov\u00e1sz proved a fundamental theorem that, for a graph\n            <jats:italic>H<\/jats:italic>\n            given by its 0-1 valued adjacency matrix, the graph homomorphism function\n            <jats:italic>G<\/jats:italic>\n            \u21a6 hom(\n            <jats:italic>G<\/jats:italic>\n            ,\n            <jats:italic>H<\/jats:italic>\n            ) determines the isomorphism type of\n            <jats:italic>H<\/jats:italic>\n            . In the past 50 years, various extensions have been proved by many researchers\u00a0[1, 15, 21, 24, 26]. These extend the basic 0-1 case to admit vertex and edge weights; but these extensions all have some restrictions such as all vertex weights must be positive. In this article, we prove a general form of this theorem where\n            <jats:italic>H<\/jats:italic>\n            can have arbitrary vertex and edge weights. A noteworthy aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism\n            <jats:italic>effective<\/jats:italic>\n            in the following sense: it provides an algorithm that for any\n            <jats:italic>H<\/jats:italic>\n            either outputs a P-time algorithm solving hom(&amp;sdot,\n            <jats:italic>H<\/jats:italic>\n            ) or a P-time reduction from a canonical #P-hard problem to hom(&amp;sdot,\n            <jats:italic>H<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/3448641","type":"journal-article","created":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T13:37:45Z","timestamp":1622813865000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["On a Theorem of Lov\u00e1sz that (&amp;sdot,\n            <i>H<\/i>\n            ) Determines the Isomorphism Type of\n            <i>H<\/i>"],"prefix":"10.1145","volume":"13","author":[{"given":"Jin-yi","family":"Cai","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, Wisconsin, USA"}]},{"given":"Artem","family":"Govorov","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, Wisconsin, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.07.008"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.011"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781107477063"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-019-00184-5"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/110840194"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2020.104589"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01305232"},{"volume-title":"Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919)","author":"Cai J.-Y.","key":"e_1_2_1_8_1","unstructured":"J.-Y. Cai and A. Govorov . 2019. Perfect matchings, rank of connection tensors and graph homomorphisms . In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919) . 476\u2013495. J.-Y. Cai and A. Govorov. 2019. Perfect matchings, rank of connection tensors and graph homomorphisms. In Proceedings of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201919). 476\u2013495."},{"volume-title":"Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS\u201920)","author":"Cai J.-Y.","key":"e_1_2_1_9_1","unstructured":"J.-Y. Cai and A. Govorov . 2020. On a theorem of Lov\u00e1sz that hom(&sdot, H) determines the isomorphism type of . In Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS\u201920) . 17:1\u201317:15. J.-Y. Cai and A. Govorov. 2020. On a theorem of Lov\u00e1sz that hom(&sdot, H) determines the isomorphism type of . In Proceedings of the 11th Innovations in Theoretical Computer Science (ITCS\u201920). 17:1\u201317:15."},{"volume-title":"Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP\u201918)","author":"Dell H.","key":"e_1_2_1_10_1","unstructured":"H. Dell , M. Grohe , and G. Rattan . 2018. Lov\u00e1sz meets Weisfeiler and Leman . In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP\u201918) . 40:1\u201340:14. H. Dell, M. Grohe, and G. Rattan. 2018. Lov\u00e1sz meets Weisfeiler and Leman. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP\u201918). 40:1\u201340:14."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20461"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1314690.1314691"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/360708.360731"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20036"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-06-00529-7"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/090757496"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2016.01.022"},{"key":"e_1_2_1_18_1","volume-title":"Grohe and J. Makowsky (Eds.)","volume":"558","author":"Grohe M.","unstructured":"M. Grohe and M. Thurley . 2011. Counting homomorphisms and partition functions. In Model Theoretic Methods in Finite Combinatorics (Contemporary Mathematics), M . Grohe and J. Makowsky (Eds.) , Vol. 558 . American Mathematical Society, 243\u2013292. M. Grohe and M. Thurley. 2011. Counting homomorphisms and partition functions. In Model Theoretic Methods in Finite Combinatorics (Contemporary Mathematics), M. Grohe and J. Makowsky (Eds.), Vol. 558. American Mathematical Society, 243\u2013292."},{"key":"e_1_2_1_19_1","unstructured":"P. Hell and J. Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications Vol. 28. Oxford University Press.  P. Hell and J. Ne\u0161et\u0159il. 2004. Graphs and Homomorphisms. Oxford Lecture Series in Mathematics and its Applications Vol. 28. Oxford University Press."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02280291"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2005.04.012"},{"key":"e_1_2_1_22_1","volume-title":"On the dimension of graph algebras for homomorphism functions. Retrieved from on","author":"Lov\u00e1sz L.","year":"2021","unstructured":"L. Lov\u00e1sz . 2013. On the dimension of graph algebras for homomorphism functions. Retrieved from on April 25, 2021 https:\/\/web.cs.elte.hu\/\u223clovasz\/book\/homnotes-6-4-1.pdf. L. Lov\u00e1sz. 2013. On the dimension of graph algebras for homomorphism functions. Retrieved from on April 25, 2021 https:\/\/web.cs.elte.hu\/\u223clovasz\/book\/homnotes-6-4-1.pdf."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2007.06.005"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1462073.1462075"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2008.10.003"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.indag.2013.04.004"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-07-00568-1"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/070682575"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448641","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448641","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3448641","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:43Z","timestamp":1750193263000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3448641"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,4]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3448641"],"URL":"https:\/\/doi.org\/10.1145\/3448641","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"type":"print","value":"1942-3454"},{"type":"electronic","value":"1942-3462"}],"subject":[],"published":{"date-parts":[[2021,6,4]]},"assertion":[{"value":"2020-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-06-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}