Spectral criteria clarify planar graph homomorphism complexity classes
Spectral Methods for the Complexity of Planar Graph Homomorphisms
Computational Complexity
Summary
Understanding how to count graph homomorphisms, which are ways of mapping one graph's points to another, helps solve many problems in computer science. The authors study this problem specifically for planar graphs, those that can be drawn without crossing edges. They use spectral properties (related to eigenvalues of matrices) to decide when counting these mappings is very hard versus when it is easy or possible in polynomial time. Their work classifies all such planar cases for certain matrix types, connecting previously known polynomial-time methods with proofs of hardness.
What this means in practice
- •For graph algorithm developers: Identify which planar graph homomorphism problems are efficiently solvable or #P-hard to guide algorithm design choices.
- •For computational complexity analysts: Use spectral and determinant criteria to prove hardness or tractability boundaries in planar graph computation problems.
A theory result. No direct application yet.
Authors
Ashwin Maran, Jin-Yi Cai, Zhuxiao Tang
Abstract
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.