Planar graph counting complexity classified using matrix algebra
Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph Homomorphisms (Part I)
Computational Complexity
Summary
This paper studies how hard it is to count certain types of patterns called planar graph homomorphisms when weights are given by a matrix. The authors show that depending on the matrix, the counting problem is either easy everywhere, hard everywhere, or only hard in some cases but easier for planar graphs using special algorithms. They develop a new mathematical tool called a logarithmic matrix algebra to categorize these cases. This is Part I, focusing on positive and positive definite matrices, which is a crucial step toward the full classification.
What this means in practice
- •For algorithm designers: Use the classification to identify when planar graph counting problems admit efficient algorithms based on the matrix weights involved.
- •For complexity theorists: Apply the dichotomy framework to understand which counting problems over planar graphs are computationally feasible or inherently difficult.
A theory result. No direct application yet.
Authors
Jin-Yi Cai, Zhuxiao Tang
Abstract
We prove a complexity classification of counting planar graph homomorphisms with non-negative weights. For a real symmetric matrix $M$ with non-negative entries, the problem $\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 that involve the P-time FKT algorithm to count planar perfect matchings with a holographic transformation. The dichotomy is achieved by forming a (centered) logarithmic matrix algebra (a vector space with bilinear multiplication) by taking entrywise logarithms of all realizable matrices from $M$ using planar edge gadgets and polynomial interpolation. The current version is part I, which contains the proof for the dichotomy of entrywise positive and positive definite matrices, which is at the core of the dichotomy for non-negative matrices. Part II contains the extension from entrywise positive and positive definite matrices to non-negative matrices.