2026-07-24T05:17:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12473 2024-03-06T10:50:14Z ddc:004 open_access

A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights Govorov, Artem Cai, Jin-Yi Dyer, Martin Graph homomorphism Complexity dichotomy Counting problems We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z_A(⋅), also known as the partition function. Dyer and Greenhill [Martin E. Dyer and Catherine S. Greenhill, 2000] established a complexity dichotomy of Z_A(⋅) for symmetric {0, 1}-matrices A, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [Andrei Bulatov and Martin Grohe, 2005] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices A. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric A, either Z_A(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [Leslie A. Goldberg et al., 2010] for Z_A(⋅) also holds for simple graphs, where A is any real symmetric matrix. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Artem Govorov and Jin-Yi Cai and Martin Dyer 2020 Is Part Of LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2020.66 urn:nbn:de:0030-drops-124733 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.66 eng https://creativecommons.org/licenses/by/3.0/legalcode