2026-07-21T14:19:30Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:19790 2024-03-14T08:42:35Z ddc:004 open_access
When Do Homomorphism Counts Help in Query Algorithms? ten Cate, Balder Dalmau, Victor Kolaitis, Phokion G. Wu, Wei-Lin query algorithms homomorphism homomorphism counts conjunctive query constraint satisfaction A query algorithm based on homomorphism counts is a procedure for determining whether a given instance satisfies a property by counting homomorphisms between the given instance and finitely many predetermined instances. In a left query algorithm, we count homomorphisms from the predetermined instances to the given instance, while in a right query algorithm we count homomorphisms from the given instance to the predetermined instances. Homomorphisms are usually counted over the semiring β„• of non-negative integers; it is also meaningful, however, to count homomorphisms over the Boolean semiring 𝔹, in which case the homomorphism count indicates whether or not a homomorphism exists. We first characterize the properties that admit a left query algorithm over 𝔹 by showing that these are precisely the properties that are both first-order definable and closed under homomorphic equivalence. After this, we turn attention to a comparison between left query algorithms over 𝔹 and left query algorithms over β„•. In general, there are properties that admit a left query algorithm over β„• but not over 𝔹. The main result of this paper asserts that if a property is closed under homomorphic equivalence, then that property admits a left query algorithm over 𝔹 if and only if it admits a left query algorithm over β„•. In other words and rather surprisingly, homomorphism counts over β„• do not help as regards properties that are closed under homomorphic equivalence. Finally, we characterize the properties that admit both a left query algorithm over 𝔹 and a right query algorithm over 𝔹. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Balder ten Cate and Victor Dalmau and Phokion G. Kolaitis and Wei-Lin Wu 2024 Is Part Of LIPIcs, Volume 290, 27th International Conference on Database Theory (ICDT 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2024.8 urn:nbn:de:0030-drops-197905 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2024.8 eng https://creativecommons.org/licenses/by/4.0/legalcode