{"ID":2828827,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2512.13058","arxiv_id":"2512.13058","title":"Homomorphism Indistinguishability, Multiplicity Automata Equivalence, and Polynomial Identity Testing","abstract":"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.","short_abstract":"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 ove...","url_abs":"https://arxiv.org/abs/2512.13058","url_pdf":"https://arxiv.org/pdf/2512.13058v1","authors":"[\"Marek Černý\",\"Tim Seppelt\"]","published":"2025-12-15T07:36:44Z","proceeding":"cs.CC","tasks":"[\"cs.CC\",\"cs.DM\",\"cs.DS\",\"cs.LO\"]","methods":"[]","has_code":false}