CS Paper Radar

A Dichotomy for Planar Graph Homomorphisms with Nonnegative Weights

Chenghua Liu, Boning Meng

cs.CC ·submitted 2026-10-04 17:51 UTC · v1
theorycode/data

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.

Comment
29 pages. Lean 4 formalization: https://github.com/liuchliuch/planar-homomorphisms-lean

Closest papers

Nearest neighbours by meaning across the whole index.

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph Homomorphisms

cs.CC ·2026-09-30 ·Jin-Yi Cai, Zhuxiao Tang
theory similarity 0.68
Abstract · 93 pages, 6 figures

We prove a complexity classification of counting planar graph homomorphisms with non-negative weights. For a real symmetric matrix $M$ with nonnegative entries, the problem $\GH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs. Furthermore, $\GH(M)$ in (2) consists of precisely those that involve the P-time FKT algorithm to count planar perfect matchings with a holographic transformation. The dichotomy for entrywise positive and full rank matrices lies at the core of the proof. In this setting, the main tool is a matrix algebra ${A}$ (a vector space with bilinear multiplication) formed by taking the real span of (centered) entrywise logarithms of all realizable matrices from $M$ using planar edge gadgets and polynomial interpolation. We then define a multiplicative homomorphism $F(\cdot)$ on the algebra ${A}$, which turns out to be a polynomial map. The exponents of prime factorization of component polynomials of $F$ induce graph distances for distance-regular graphs. These graphs are either the Hamming graphs or Doob graphs using a classification result for distance-regular graphs (if $\PlGH(M)$ is not \#P-hard), after obtaining their intersection numbers. The dichotomy is proved in either case. We then extend the complexity classification to all nonnegative matrices.

0.38

Spectral Methods for the Complexity of Planar Graph Homomorphisms

cs.CC ·2026-09-28 ·Ashwin Maran, Jin-Yi Cai, Zhuxiao Tang
theory similarity 0.60
Abstract · 35 pages, 2 figures

We explore the frontier beyond the recently discovered barrier represented by the \emph{quantum automorphism group} $qut(M)$ in the classification theory of planar graph homomorphisms $PlGH(M)$. We show that analyzing the spectral relations of $M$ can prove \#P-hardness when traditional vertex separation and domain-reduction methods with planar edge gadgets provably fail due to the $\qut(M)$ barrier. We prove two criteria of \#P-hardness for $PlGH(M)$: a spectral criterion and a determinant criterion. It is known that the core problem for the classification of $PlGH(M)$ for nonnegative matrices $M$ is for positive definite entry-wise positive matrices. We use the spectral criterion to show that $PlGH(M)$ is \#P-hard for all circulant matrices of prime order $q \ge 3$, while for $q=2$ it is precisely the matchgate case and is P-time computable by the FKT algorithm (for planar perfect matching). We also prove a complexity dichotomy for $\PlGH$ problems defined by tensor products of 2 by 2 matrices. This gives a complete complexity classification for this class of matrices, and the FKT algorithm together with a holographic transformation is \emph{universal}---every $PlGH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs; furthermore, $PlGH(M)$ in (2) consists of precisely those computable by FKT with a holographic transformation.

0.30

An Almost-tight Size Lower Bound for Bounded Treewidth Homomorphism-Distinguishability

cs.DM ·2026-11-02 ·Moritz Lichter, Harry Vinall-Smeeth
theory similarity 0.60
Abstract · 66 pages

One way to compare two graphs $G_1, G_2$ is to check whether there is some graph $H$ in a graph class $\mathcal{H}$, such that the number of homomorphisms from $H$ to $G_1$ is not equal to that from $H$ to $G_2$. This is the field of homomorphism distinguishability which has gained a lot of traction in recent years. In this paper, we study the case where $\mathcal{H}$ is the class of graphs of treewidth $k$. This has connections to important concepts in logic, machine learning, combinatorial optimization and proof complexity. In particular, Dvořák showed that $G_1$ and $G_2$ can be distinguished by a homomorphism count from a graph of treewidth $k$ iff $G_1$ and $G_2$ are distinguishable by the $k$-dimensional Weisfeiler-Leman algorithm. While the relation between the iteration number of this algorithm and the depth of the tree-decomposition of a distinguishing graph is understood, our understanding of the \emph{size} of $H$ is limited. We show a $2^{Ω(n^{k/2})}$ lower bound on the size of a graph of treewidth $k$ required to distinguish two graphs of order $n$. This bound is proved via a new combinatorial game along with a construction which uses a recent compression technique for CFI graphs. It is almost tight to the known $2^{O(n^{k+1})}$ upper bound and is an exponential improvement on the previous best known lower bound.

0.25

The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths

cs.DS ·2026-10-13 ·Hitendra Kumar, Mathieu Mari, R. B. Sandeep
theory similarity 0.58
Abstract · added acknowledgement

Fix a set $S$ of positive integers. An $S$-Hamiltonian cycle is a cyclic ordering of all vertices of a graph such that each consecutive pair is joined by a walk whose length belongs to $S$. We study the complexity of deciding whether an input graph admits such an ordering, together with the corresponding path variants with prescribed or unrestricted endpoints. We complete the complexity classification for undirected graphs. In particular, we prove NP-completeness for every finite nonempty set of odd lengths, resolving an open problem posed by Amarilli, Lombardo, and Monet (WG 2026). For digraphs, all three problems are NP-complete for every fixed finite nonempty $S$ and admit linear-time algorithms when $S$ is cofinite. For other fixed infinite sets $S$, we establish NP-complete and undecidable cases, with undecidability occurring even when $S$ is recursive.

0.23

A Full Complexity Dichotomy for Complex-Valued Boolean Holant Problems

cs.CC ·2026-09-06 ·Chenghua Liu, Boning Meng, Juqiu Wang
theory similarity 0.58
Abstract · 98 pages; proof and exposition revised, Lean repository linked

A Boolean Holant problem evaluates a graph partition function specified by local signatures at its vertices. We prove a complexity dichotomy for arbitrary finite sets of algebraic complex-valued signatures on general graphs: an explicit, decidable criterion characterizes the polynomial-time cases, and every remaining case is $\#\mathsf{P}$-hard under polynomial-time Turing reductions. The proof resolves the all-even case by constructing signatures with nonzero endpoints and all remaining support on the central layer, then classifying them according to half their arity. Binary transfer groups and matching-product reconstruction provide the main tools in the small- and large-height cases, respectively.

0.24

A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability

cs.LO cs.CCmath.CO ·2026-08-13 ·Radu Curticapean, Daniel Neuen, Amir Nikabadi, Tim Seppelt, Ben Young
theory similarity 0.58
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 in $\mathcal{F}$. A wide range of relaxations of graph isomorphism arise this way: isomorphism itself over the class of all graphs [Lovász, Acta Math. Hung. 1967], equivalence under the $k$-dimensional Weisfeiler-Leman algorithm over the graphs of treewidth $\leq k$ [Dvořák, J. Graph Theory 2010], and quantum isomorphism over planar graphs [Mančinska-Roberson, FOCS 2020]. Since the class $\mathcal{F}$ is typically infinite, it is not clear a priori whether homomorphism indistinguishability over $\mathcal{F}$ is decidable; for planar graphs it is undecidable. Every class for which decidability was previously known is sparse. We give the first decidability results for dense graph classes: We introduce the dense Weisfeiler-Leman algorithm that decides homomorphism indistinguishability over the class of graphs of cliquewidth $\leq k$, the dense counterpart of treewidth. This relation was not previously known to be decidable. The algorithm colors $k$-tuples of vertex subsets rather than $k$-tuples of vertices. Beyond the class of all graphs of cliquewidth $\leq k$, we prove a general meta-theorem: homomorphism indistinguishability over every $\mathsf{CMSO}_1$-definable graph class of bounded cliquewidth is decidable, in randomized exponential time. For classes of bounded linear cliquewidth the bound improves to $\mathsf{PSPACE}$, and we show this is tight by exhibiting such a class for which the problem is $\mathsf{PSPACE}$-complete. These are the first general algorithms for homomorphism indistinguishability over dense graph classes.

0.33

Complexity of liveness in ring Petri nets and of halting in chip-firing on simple digraphs

cs.CC cs.DMcs.FL ·2026-10-16 ·Eike Best, Raymond Devillers, Petr Jančar, Matěj Ošťádal
similarity 0.58
Abstract

A ring Petri net (weighted circuit, cyclic weighted T-system) consists of a single directed circuit with arbitrary positive arc weights. We show that deciding liveness of ring Petri nets is coNP-complete, and that coNP-hardness holds in the strong sense already for token-conserving rings, in which every transition consumes and produces the same number of tokens. The proof is a short reduction from the covering problem for systems of residue classes (the complement of Simultaneous Incongruences). Together with a known reduction to circuits, it follows that liveness of weighted T-systems (weighted marked graphs, synchronous dataflow graphs) is coNP-complete, and coNP-hard in the strong sense. As a further consequence, the halting problem for chip-firing on simple directed graphs is NP-complete, which answers a question of Farrell and Levine. On 7 October 2026, the problem of liveness was posed to the AI model Claude Opus 5.5 (Anthropic), which found the reduction, also suggesting the application to the chip-firing problem, and wrote a first version of this paper; the human authors checked it and, together with the model, revised it iteratively into the present form.

0.24

Binary Belief Propagation Fixed Points: Finiteness, Rigidity, and Topological Complexity

cs.IT math.AGmath.CO ·2026-11-09 ·Yusuke Watanabe
theorycode/data similarity 0.57
Abstract · 37 pages, 3 figures. Lean 4 formalization and interval certificates at https://github.com/ywatanabex/bp-response-geometry-lean

A fixed finite binary Ising model has only finitely many admissible complex belief propagation fixed points, even at degenerate parameter values. Families of positive fixed points obtained by varying external fields can nevertheless have nontrivial topology. We study this distinction through the external-field projection. For a fixed field, we prove finiteness by bounding the pole orders of the magnetizations on a hypothetical complex solution curve. The generic degree on the support graph then bounds the total local multiplicity. A graph has a single smooth real line as its full positive response for every choice of positive couplings, base field, and strictly positive sweep direction exactly when it contains no two vertex-disjoint connected subgraphs of cycle rank at least two. Two such subgraphs suffice to create a circular component. For a plane obtained by varying two vertex fields, connected simple bipartite cubic graphs with one uniform coupling and a universal bound on the fixed fields realize every genus. The minimum number of vertices grows logarithmically in the genus, by a matching algebraic upper bound on Betti numbers. Finally, we certify the complete field discriminant of an eighteen-vertex product model and recover its torus component's genus from the counts of distinct roots on all field cells. The three main theorems, including the logarithmic size bounds, are formally verified in Lean 4 with Mathlib.

0.31