A dichotomy for bounded degree graph homomorphisms with nonnegative weights

A Govorov, JY Cai, M Dyer - Journal of Computer and System Sciences, 2023 - Elsevier
A Govorov, JY Cai, M Dyer
Journal of Computer and System Sciences, 2023Elsevier
Each symmetric matrix A defines a graph homomorphism function ZA (⋅), also known as the
partition function. We prove that the Bulatov-Grohe dichotomy [4] for ZA (⋅) holds for
bounded degree graphs. This resolves a problem that has been open for 15 years.
Specifically, we prove that for any nonnegative symmetric matrix A with algebraic entries,
either ZA (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 …
Each symmetric matrix A defines a graph homomorphism function Z A (⋅), also known as the partition function. We prove that the Bulatov-Grohe dichotomy [4] for Z A (⋅) holds for bounded degree graphs. This resolves a problem that has been open for 15 years. Specifically, we prove that for any nonnegative symmetric matrix A with algebraic entries, 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.[12] for Z A (⋅) also holds for simple graphs, where A is any real symmetric matrix.
Elsevier