Planar graph homomorphism counting complexity fully classified
A Dichotomy for Planar Graph Homomorphisms with Nonnegative Weights
Computational Complexity
Summary
This paper solves a puzzle about how hard it is to count certain mathematical mappings called planar graph homomorphisms when weighted by fixed nonnegative numbers. The authors find a clear dividing line between easy and hard counting problems depending on the weights used. They use advanced math tools from geometry and entropy to understand when these problems can be solved efficiently. Their results also apply to related models in physics and computer science. Moreover, the proofs have been checked for correctness using formal software.
What this means in practice
- •For complexity theorists: Determine whether specific planar graph homomorphism counting problems with given weights are computationally tractable or hard.
- •For statistical physics modelers: Identify exactly when certain planar Ising and clock models can be efficiently analyzed based on their interaction parameters.
A theory result. No direct application yet.
Authors
Chenghua Liu, Boning Meng
Abstract
We prove a complete complexity dichotomy for planar graph homomorphism counting with any fixed symmetric nonnegative matrix of arbitrary finite order, giving an explicit criterion for tractability. We also characterize exactly which fixed positive vertex weights preserve tractability, with both classifications extending from algebraic weights to fixed real weights in a prescribed exact representation. Our proof hinges on an entropy-based continuation argument: maximal logarithmic support identifies distance kernels as maximum-entropy completions, extending their positive definiteness throughout the parameter interval. This enables distance geometry to recover hidden product coordinates even when planar gadgets cannot distinguish colors; counting-hardness arguments then force the factors to be zero-field Boolean Ising interactions. The classification also yields complete tractability criteria for clock models, coupled Ising systems, and planar contractions of stoquastic imaginary-time kernels. All results have been formally verified in Lean 4.