2026-07-23T23:57:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20638 2024-08-23T05:50:30Z ddc:004 open_access

An Algorithmic Meta Theorem for Homomorphism Indistinguishability Seppelt, Tim homomorphism indistinguishability graph homomorphism graph minor recognisability randomised algorithm Courcelle’s Theorem Two graphs G and H are homomorphism indistinguishable over a family of graphs ℱ if for all graphs 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. The wealth of such results motivates a more fundamental study of homomorphism indistinguishability. From a computational perspective, the central object of interest is the decision problem HomInd(ℱ) which asks to determine whether two input graphs G and H are homomorphism indistinguishable over a fixed graph class ℱ. The problem HomInd(ℱ) is known to be decidable only for few graph classes ℱ. Due to a conjecture by Roberson (2022) and results by Seppelt (MFCS 2023), homomorphism indistinguishability relations over minor-closed graph classes are of special interest. We show that HomInd(ℱ) admits a randomised polynomial-time algorithm for every minor-closed graph class ℱ of bounded treewidth. This result extends to a version of HomInd where the graph class ℱ is specified by a sentence in counting monadic second-order logic 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tim Seppelt 2024 Is Part Of LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2024.82 urn:nbn:de:0030-drops-206387 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.82 eng https://creativecommons.org/licenses/by/4.0/legalcode