# An Algorithmic Meta Theorem for Homomorphism Indistinguishability

arXiv: https://arxiv.org/abs/2402.08989 · HTML: https://mlsanity.com/paper/2402.08989/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Feb 2024.

## Built on by (most cited first, 1 of 1)

- [Caterpillar GNN: Replacing Message Passing with Efficient Aggregation](https://mlsanity.com/paper/2506.06784/) (2025)

## Abstract (arXiv)

Two graphs G and H are homomorphism indistinguishable over a family of graphs F if for all graphs F ∈ F the number of homomorphisms from F to G is equal to the number of homomorphism from F to H. Many natural equivalence relations comparing graphs such as (quantum) isomorphism, cospectrality, and logical equivalences can be characterised as homomorphism indistinguishability relations over various graph classes. For a fixed graph class F, the decision problem HomInd(F) asks to determine whether two input graphs G and H are homomorphism indistinguishable over F. The problem HomInd(F) is known to be decidable only for few graph classes F. We show that HomInd(F) admits a randomised polynomial-time algorithm for every graph class F of bounded treewidth which is definable in counting monadic second-order logic CMSO2. Thereby, we give the first general algorithm for deciding homomorphism indistinguishability. This result extends to a version of HomInd where the graph class F is specified by a CMSO2-sentence and a bound k on the treewidth, which are given as input. For fixed k, this problem is randomised fixed-parameter tractable. If k is part of the input then it is coNP- and coW[1]-hard. Addressing a problem posed by Berkholz (2012), we show coNP-hardness by establishing that deciding indistinguishability under the k-dimensional Weisfeiler--Leman algorithm is coNP-hard when k is part of the input.