Adaptive query algorithms for relational structures based on homomorphism counts

DOI10.4230/LIPICS.MFCS.2025.34MaRDI QIDQ7310198zbMATH OpenFDO

Authors Balder ten Cate, Phokion G. Kolaitis, Arnar Á. Kristjánsson

Publication date 5 August 2026

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.MFCS.2025.34

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Characterisation of First-Order Constraint Satisfaction Problems
• An optimal lower bound on the number of variables for graph identification
• Counting bounded tree depth homomorphisms
• scientific article; zbMATH DE number 1461253 (Why is no real title available?)
• scientific article; zbMATH DE number 2117181 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Logical equivalences, homomorphism indistinguishability, and forbidden minors
• On algorithms based on finitely many homomorphism counts
• On recognizing graphs by numbers of homomorphisms
• Operations with structures
• Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs
• Regular families of forests, antichains and duality pairs of relational structures
• Right-adjoints for Datalog programs
• Undecidable optimization problems for database logic programs
• When do homomorphism counts help in query algorithms?

This page was built for publication: Adaptive query algorithms for relational structures based on homomorphism counts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7310198)