On algorithms based on finitely many homomorphism counts

DOI10.1016/J.IC.2025.105326MaRDI QIDQ6931988zbMATH OpenFDO

Authors Yijia Chen, Jörg Flum, Mingjun Liu, Zhiyang Xun

Publication date 9 September 2025

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.IC.2025.105326

zbMATH Keywords

adaptive query algorithmshom algorithm

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Graph algorithms (graph-theoretic aspects) (05C85)

Cites work

• An optimal lower bound on the number of variables for graph identification
• Counting bounded tree depth homomorphisms
• FO-Definability of Shrub-Depth
• Forbidden subgraphs in terms of forbidden quantifiers
• Graph Theory and Probability
• Homomorphisms are a good basis for counting small subgraphs
• Large networks and graph limits
• Lov\'asz Meets Weisfeiler and Leman
• On recognizing graphs by numbers of homomorphisms
• On the cancellation law among finite relational structures
• Operations with structures
• Subgraphs and well‐quasi‐ordering
• The Complexity of Homomorphism Indistinguishability
• Tree-depth, quantifier elimination, and quantifier rank
• When trees grow low: shrubs and fast \(\mathrm{MSO}_{1}\)

This page was built for publication: On algorithms based on finitely many homomorphism counts

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