2026-09-28T18:31:49Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10998 2026-09-23T07:56:37Z ddc:004 open_access

The Complexity of Homomorphism Indistinguishability Böker, Jan Chen, Yijia Grohe, Martin Rattan, Gaurav graph homomorphism numbers counting complexity treewidth For every graph class {F}, let HomInd({F}) be the problem of deciding whether two given graphs are homomorphism-indistinguishable over {F}, i.e., for every graph F in {F}, the number hom(F, G) of homomorphisms from F to G equals the corresponding number hom(F, H) for H. For several natural graph classes (such as paths, trees, bounded treewidth graphs), homomorphism-indistinguishability over the class has an efficient structural characterization, resulting in polynomial time solvability [H. Dell et al., 2018]. In particular, it is known that two non-isomorphic graphs are homomorphism-indistinguishable over the class {T}_k of graphs of treewidth k if and only if they are not distinguished by k-dimensional Weisfeiler-Leman algorithm, a central heuristic for isomorphism testing: this characterization implies a polynomial time algorithm for HomInd({T}_k), for every fixed k in N. In this paper, we show that there is a polynomial-time-decidable class {F} of undirected graphs of bounded treewidth such that HomInd({F}) is undecidable. Our second hardness result concerns the class {K} of complete graphs. We show that HomInd({K}) is co-NP-hard, and in fact, we show completeness for the class C_=P (under P-time Turing reductions). On the algorithmic side, we show that HomInd({P}) can be solved in polynomial time for the class {P} of directed paths. We end with a brief study of two variants of the HomInd({F}) problem: (a) the problem of lexographic-comparison of homomorphism numbers of two graphs, and (b) the problem of computing certain distance-measures (defined via homomorphism numbers) between two graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Böker and Yijia Chen and Martin Grohe and Gaurav Rattan 2019 Is Part Of LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2019.54 urn:nbn:de:0030-drops-109980 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.54 eng https://creativecommons.org/licenses/by/3.0/legalcode