{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T02:49:31Z","timestamp":1773629371359,"version":"3.50.1"},"reference-count":68,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"European Research Council","award":["101077083"],"award-info":[{"award-number":["101077083"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Comput. Theory"],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>\n                    Representing graphs by their homomorphism counts has led to the beautiful theory of homomorphism indistinguishability in recent years. Moreover, homomorphism counts have promising applications in database theory and machine learning, where one would like to answer queries or classify graphs solely based on the representation of a graph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    as a finite vector of homomorphism counts from some fixed finite set of graphs to\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    . We study the computational complexity of the arguably most fundamental computational problem associated to these representations, the\n                    <jats:italic toggle=\"yes\">homomorphism reconstructibility problem<\/jats:italic>\n                    : given a finite sequence of graphs and a corresponding vector of natural numbers, decide whether there exists a graph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    that realises the given vector as the homomorphism counts from the given graphs.\n                  <\/jats:p>\n                  <jats:p>\n                    We show that this problem yields a natural example of an\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {NP}^{\\#\\mathsf {P}}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -hard problem, which still can be\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {NP}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -hard when restricted to a fixed number of input graphs of bounded treewidth and a fixed input vector of natural numbers, or alternatively, when restricted to a finite input set of graphs. We further show that, when restricted to a finite input set of graphs and given an upper bound on the order of the graph\n                    <jats:italic toggle=\"yes\">G<\/jats:italic>\n                    as additional input, the problem cannot be\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {NP}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    -hard unless\n                    <jats:inline-formula content-type=\"math\/tex\">\n                      <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\(\\mathsf {P}= \\mathsf {NP}\\)<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    . For this regime, we obtain partial positive results. We also investigate the problem\u2019s parameterised complexity and provide fpt-algorithms for the case that a single graph is given and that multiple graphs of the same order with subgraph instead of homomorphism counts are given.\n                  <\/jats:p>","DOI":"10.1145\/3762196","type":"journal-article","created":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T11:26:56Z","timestamp":1755516416000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Complexity of Homomorphism Reconstructibility"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4584-121X","authenticated-orcid":false,"given":"Jan","family":"B\u00f6ker","sequence":"first","affiliation":[{"name":"Chair for Logic and Theory of Discrete Systems, RWTH Aachen University","place":["Aachen, Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-3446-5874","authenticated-orcid":false,"given":"Louis","family":"H\u00e4rtel","sequence":"additional","affiliation":[{"name":"Chair for Logic and Theory of Discrete Systems, RWTH Aachen University","place":["Aachen, Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0009-0000-4547-1023","authenticated-orcid":false,"given":"Nina","family":"Runde","sequence":"additional","affiliation":[{"name":"Chair for Logic and Theory of Discrete Systems, RWTH Aachen University","place":["Aachen, Germany"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6447-0568","authenticated-orcid":false,"given":"Tim","family":"Seppelt","sequence":"additional","affiliation":[{"name":"Chair for Logic and Theory of Discrete Systems, RWTH Aachen University","place":["Aachen, Germany"]},{"name":"IT-Universitet i K\u00f8benhavn","place":["Copenhagen, Denmark"]}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3034-730X","authenticated-orcid":false,"given":"Christoph","family":"Standke","sequence":"additional","affiliation":[{"name":"Chair for Logic and Theory of Discrete Systems, RWTH Aachen University","place":["Aachen, Germany"]}]}],"member":"320","published-online":{"date-parts":[[2026,3,5]]},"reference":[{"key":"e_1_3_3_2_2","volume-title":"Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables","author":"Abramowitz Milton","year":"1965","unstructured":"Milton Abramowitz and Irene A. Stegun. 1965. Handbook of Mathematical Functions: With Formulas, Graphs, and Mathematical Tables. Dover Publications, New York."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-10736-8_2"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470543"},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2019.54"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","unstructured":"Jan B\u00f6ker Louis H\u00e4rtel Nina Runde Tim Seppelt and Christoph Standke. 2023. The complexity of homomorphism reconstructibility. arXiv:2310.09009. Retrieved from https:\/\/arxiv.org\/abs\/2310.09009DOI:10.48550\/ARXIV.2310.09009","DOI":"10.48550\/ARXIV.2310.09009"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2024.19"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3379445"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3154319"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/153850.153856"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.MFCS.2022.32"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2016.47"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055502"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.22"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.08.008"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/LICS52264.2021.9470609"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","unstructured":"Holger Dell Martin Grohe and Gaurav Rattan. 2018. Lov\u00e1sz meets weisfeiler and leman. In 45th International Colloquium on Automata Languages and Programming (ICALP 2018) (Leibniz International Proceedings in Informatics (LIPIcs)) Ioannis Chatzigiannakis Christos Kaklamanis D\u00e1niel Marx and Donald Sannella (Eds.). Schloss Dagstuhl Leibniz-Zentrum f\u00fcr Informatik Dagstuhl Germany 40:1-40:14. DOI:10.4230\/LIPIcs.ICALP.2018.40","DOI":"10.4230\/LIPIcs.ICALP.2018.40"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20461"},{"key":"e_1_3_3_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80024-8"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-29953-X"},{"key":"e_1_3_3_22_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-06-00529-7"},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(76)90059-1"},{"key":"e_1_3_3_24_2","unstructured":"Roman Glebov Andrzej Grzesik Ping Hu Tam\u00e1s Hubai Daniel Kr\u00e1l\u2019 and Jan Volec. 2017. Densities of 3-vertex graphs. (April2017). arXiv:1610.02446. Retrieved from http:\/\/arxiv.org\/abs\/1610.02446"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/3373718.3394739"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375395.3387641"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.70"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2022.3214832"},{"key":"e_1_3_3_29_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-94-015-8937-6_4"},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0894-0347-2010-00687-X"},{"key":"e_1_3_3_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/203610.203611"},{"key":"e_1_3_3_32_2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.21762"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/211414.211419"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01464230"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-8176-4842-8_27"},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200064"},{"key":"e_1_3_3_37_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.03.009"},{"key":"e_1_3_3_38_2","doi-asserted-by":"publisher","DOI":"10.1525\/9780520319875-014"},{"key":"e_1_3_3_39_2","doi-asserted-by":"publisher","DOI":"10.1145\/3517804.3524168"},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1287\/moor.8.4.538"},{"key":"e_1_3_3_41_2","first-page":"3","article-title":"Coverings and colorings of hypergraphs","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1973","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 1973. Coverings and colorings of hypergraphs. Proc. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing (1973), 3\u201312. Retrieved from https:\/\/zbmath.org\/0322.05114","journal-title":"Proc. 4th Southeastern Conference of Combinatorics, Graph Theory, and Computing"},{"key":"e_1_3_3_42_2","volume-title":"Combinatorial Problems and Exercises (2nd.ed.)","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1993","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 1993. Combinatorial Problems and Exercises (2nd.ed.). Akad\u00e9miai Kiado Elsevier Pub. Co, Budapest Amsterdam London."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.37236\/80"},{"key":"e_1_3_3_44_2","doi-asserted-by":"publisher","DOI":"10.1090\/coll\/060"},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(82)90002-2"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00067"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803627"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780199233212.001.0001"},{"key":"e_1_3_3_49_2","doi-asserted-by":"publisher","DOI":"10.1007\/b98870"},{"key":"e_1_3_3_50_2","first-page":"485","article-title":"On the representation of natural numbers as a sum of terms of the form  \\({x(x+1)\\cdots (x+n-1)\/n!}\\)","author":"Ne\u010daev V. I.","year":"1953","unstructured":"V. I. Ne\u010daev. 1953. On the representation of natural numbers as a sum of terms of the form \\({x(x+1)\\cdots (x+n-1)\/n!}\\) . Izvestiya Akad. Nauk SSSR. Ser. Mat. 17, 6 (1953), 485\u2013498. Retrieved from https:\/\/www.mathnet.ru\/eng\/im3481","journal-title":"Izvestiya Akad. Nauk SSSR. Ser. Mat."},{"key":"e_1_3_3_51_2","first-page":"195","article-title":"On the question of representing natural numbers by a sum of terms of the form  \\(x(x+1)\\ldots (x+n-1)\/n!\\)","volume":"142","author":"Ne\u010daev V. I.","year":"1976","unstructured":"V. I. Ne\u010daev. 1976. On the question of representing natural numbers by a sum of terms of the form \\(x(x+1)\\ldots (x+n-1)\/n!\\) . Trudy Matematicheskogo Instituta imeni VA Steklova 142 (1976), 195\u2013197. Retrieved from https:\/\/www.mathnet.ru\/eng\/tm2571Number theory, mathematical analysis and their applications.","journal-title":"Trudy Matematicheskogo Instituta imeni VA Steklova"},{"key":"e_1_3_3_52_2","first-page":"7306","volume-title":"Proceedings of the 37th International Conference on Machine Learning, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research)","author":"Nguyen Hoang","year":"2020","unstructured":"Hoang Nguyen and Takanori Maehara. 2020. Graph homomorphism convolution. In Proceedings of the 37th International Conference on Machine Learning, 13-18 July 2020, Virtual Event (Proceedings of Machine Learning Research). PMLR, 7306\u20137316. Retrieved from http:\/\/proceedings.mlr.press\/v119\/nguyen20c.html"},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.2307\/2316851"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01831114"},{"key":"e_1_3_3_55_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspl.1843.0223"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009085"},{"key":"e_1_3_3_57_2","unstructured":"David E. Roberson. 2022. Oddomorphisms and homomorphism indistinguishability over graphs of bounded degree. (June2022). arXiv:2206.10321. Retrieved from http:\/\/arxiv.org\/abs\/2206.10321"},{"key":"e_1_3_3_58_2","doi-asserted-by":"publisher","DOI":"10.46298\/theoretics.24.20"},{"key":"e_1_3_3_59_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.133"},{"key":"e_1_3_3_60_2","first-page":"322","volume-title":"Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, University of Edinburgh, UK, July 20-23, 1976.","author":"Schnorr Claus-Peter","year":"1976","unstructured":"Claus-Peter Schnorr. 1976. Optimal algorithms for self-reducible problems. In Proceedings of the 3rd International Colloquium on Automata, Languages and Programming, University of Edinburgh, UK, July 20-23, 1976.S. Michaelson and Robin Milner (Eds.), Edinburgh University Press, 322\u2013337."},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2024.105224"},{"key":"e_1_3_3_62_2","volume-title":"On Some Central Problems in Computational Complexity","author":"Simon Janos","year":"1975","unstructured":"Janos Simon. 1975. On Some Central Problems in Computational Complexity. Ph. D. Dissertation. Cornell University, USA."},{"key":"e_1_3_3_63_2","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_3_3_64_2","doi-asserted-by":"publisher","DOI":"10.1137\/0220053"},{"key":"e_1_3_3_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116858"},{"key":"e_1_3_3_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00289117"},{"key":"e_1_3_3_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90141-6"},{"key":"e_1_3_3_68_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10440-006-9026-5"},{"key":"e_1_3_3_69_2","unstructured":"Hinrikus Wolf Luca Oeljeklaus Pascal K\u00fchner and Martin Grohe. 2023. Structural node embeddings with homomorphism counts. Retrieved from https:\/\/arxiv.org\/abs\/2308.15283"}],"container-title":["ACM Transactions on Computation Theory"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3762196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,16]],"date-time":"2026-03-16T01:50:52Z","timestamp":1773625852000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3762196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,5]]},"references-count":68,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3762196"],"URL":"https:\/\/doi.org\/10.1145\/3762196","relation":{},"ISSN":["1942-3454","1942-3462"],"issn-type":[{"value":"1942-3454","type":"print"},{"value":"1942-3462","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,3,5]]},"assertion":[{"value":"2024-09-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-10","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2026-03-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}