Two graphs $G$ and $H$ are homomorphism indistinguishable over a graph class $\mathcal{ F}$ if they admit the same number of homomorphisms from every graph $F \in \mathcal{ F}$. Many graph isomorphism relaxations such as (quantum) isomorphism and cospectrality can be characterised as homomorphism indistinguishability over specific graph classes. Thereby, the problems $\textrm{ HomInd}(\mathcal{ F})$ of deciding homomorphism indistinguishability over $\mathcal{ F}$ subsume diverse graph isomorphism relaxations whose complexities range from logspace to undecidable. Establishing the first general result on the complexity of $\textrm{ HomInd}(\mathcal{ F})$, Seppelt (MFCS 2024) showed that $\textrm{ HomInd}(\mathcal{ F})$ is in randomised polynomial time for every graph class $\mathcal{ F}$ of bounded treewidth that can be defined in counting monadic second-order logic $\mathsf{ CMSO}_2$. We show that this algorithm is conditionally optimal, i.e. it cannot be derandomised unless polynomial identity testing is in $\mathsf{ PTIME}$. For $\mathsf{ CMSO}_2$-definable graph classes $\mathcal{ F}$ of bounded pathwidth, we improve the previous complexity upper bound for $\textrm{ HomInd}(\mathcal{ F})$ from $\mathsf{ PTIME}$ to $\mathsf{ C}_=\mathsf{ L}$ and show that this is tight. Secondarily, we establish a connection between homomorphism indistinguishability and multiplicity automata equivalence which allows us to pinpoint the complexity of the latter problem as $\mathsf{ C}_=\mathsf{ L}$-complete.
Categories: cs.CC cs.DM cs.DS cs.LO