2026-07-22T06:27:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25514 2026-03-19T13:34:23Z ddc:004 open_access

Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing Černý, Marek Seppelt, Tim treewidth Courcelle’s theorem logspace multiplicity automata polynomial identity testing Two graphs G and H are homomorphism indistinguishable over a graph class ℱ if they admit the same number of homomorphisms from every graph F ∈ ℱ. Many graph isomorphism relaxations such as (quantum) isomorphism and cospectrality can be characterised as homomorphism indistinguishability over specific graph classes. Thereby, the problems HomInd(ℱ) of deciding homomorphism indistinguishability over ℱ subsume diverse graph isomorphism relaxations whose complexities range from logspace to undecidable. Establishing the first general result on the complexity of HomInd(ℱ), Seppelt (MFCS 2024) showed that HomInd(ℱ) is in randomised polynomial time for every graph class ℱ of bounded treewidth that can be defined in counting monadic second-order logic CMSO₂. We show that this algorithm is conditionally optimal, i.e. it cannot be derandomised unless polynomial identity testing is in P. For CMSO₂-definable graph classes ℱ of bounded pathwidth, we improve the previous complexity upper bound for HomInd(ℱ) from P to C_ = 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 C_ = L-complete. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Marek Černý and Tim Seppelt 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.25 urn:nbn:de:0030-drops-255144 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.25 eng https://creativecommons.org/licenses/by/4.0/legalcode