I&C Journal 2025 Journal Article
On algorithms based on finitely many homomorphism counts
- Yijia Chen
- Jörg Flum
- Mingjun Liu
- Zhiyang Xun
It is a well-known result of Lovász that up to isomorphism a graph G is determined by the homomorphism counts hom ( F, G ), i. e. , the number of homomorphisms from F to G, where F ranges over all graphs. Thus, in principle, we can answer any query concerning G with only accessing the hom ( ⋅, G ) 's instead of G itself. In this paper, we deal with queries φ for which there is a hom algorithm, i. e. , there are finitely many graphs F 1, …, F k such that for any graph G whether it is a Yes-instance of the query is already determined by the vector hom → F 1, …, F k ( G ): = ( hom ( F 1, G ), …, hom ( F k, G ) ), where the graphs F 1, …, F k only depend on φ. We observe that planarity of graphs and 3-colorability of graphs, properties expressible in monadic second-order logic, have no hom algorithm. We provide a characterization of the prefix classes of first-order logic with the property that each query definable by a sentence of the prefix class has a hom algorithm. For adaptive query algorithms, i. e. , algorithms that again access hom → F 1, …, F k ( G ) but here F i + 1 might depend on hom ( F 1, G ), …, hom ( F i, G ), we show that three homomorphism counts hom ( ⋅, G ) are both sufficient and in general necessary to determine the isomorphism type of G.