An Algorithmic Meta Theorem for Homomorphism Indistinguishability

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.