PaperlayerView exact revision on arXiv

Source-linked AI summary

Spectral Methods for the Complexity of Planar Graph Homomorphisms

Ashwin Maran, Jin-Yi Cai, Zhuxiao Tang

arXiv:2609.36072v1cs.CC

TL;DR

Planar graph-homomorphism hardness has been difficult to establish when quantum symmetries prevent vertex separation and domain-reduction methods. This paper combines planar edge gadgets with analytic spectral methods and gives hardness criteria. It proves hardness for prime-order circulant matrices with q ≥ 3 and a complexity boundary for tensor products of 2×2 matrices.

  • Problem

    For planar graph homomorphisms, extending complexity classifications beyond the Boolean domain is difficult, and quantum symmetries can prevent planar gadgets from separating diagonal entries.

    Source: §1 · p. 3

  • Method

    The paper combines planar edge gadgets, interpolation, and eigenvalue-relation analysis to establish spectral and determinant criteria for #P-hardness.

    Source: §1 · p. 4

  • Results

    Planar graph homomorphisms are #P-hard for positive definite circulant matrices of prime order q ≥ 3, and for tensor products of 2×2 matrices unless every factor has equal diagonal entries.

    Source: §1 · p. 4

  • Takeaways & Limitations

    Analytic and spectral methods can prove planar hardness even when traditional vertex-separation and domain-reduction methods fail.

    Source: §1 · p. 4

    The results are framed within the classical Turing machine model in terms of bit-complexity.

    Source: §2 · p. 5

Abstract

from arXiv · show

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.

1 Introduction

The introduction asks how to prove planar graph-homomorphism hardness when quantum symmetries defeat vertex separation and domain reduction. It presents spectral and determinant criteria, applies them to circulant and tensor-product matrices, and advances a route toward a broader dichotomy.

1 Introduction

  • Nontrivial quantum automorphism groups can make diagonal entries inseparable by planar gadgets, blocking standard reductions from smaller-domain hard problems.Earlier planar classifications relied on edge gadgets, while extending Boolean-domain classifications has proved difficult even for small larger domains.Source: §1 · p. 3
  • The analytic approach uses planar edge gadgets, interpolation, and eigenvalue-relation lattices to certify hardness while avoiding problematic spectral relations.Asymptotics show the relevant analytic function is not identically zero; its countably many zeros can therefore be avoided.Source: §1 · p. 4
  • The spectral-lattice criterion and an easy-to-test determinant criterion establish #P-hardness beyond the quantum-automorphism barrier.The spectral criterion compares homogeneous multiplicative relations among eigenvalues with those of the Potts model.Source: §1 · p. 4
  • Positive definite circulant matrices of prime order q ≥ 3 yield #P-hard planar graph homomorphism problems, despite lying in the quantum gap.The proof analyzes spectral relations after a large thickening and reduces from the Potts model.Source: §1 · p. 4
  • For tensor products of 2×2 matrices, planar graph homomorphism is #P-hard unless every factor has equal diagonal entries, when holographic FKT gives polynomial-time solvability.This isolates a boundary where both vertex separation and the spectral criterion fail, yet the two sides have different complexity.Source: §1 · p. 4
  • Combining planar edge gadgets with analytic and spectral methods pushes toward a universal dichotomy for planar graph homomorphisms.The paper frames this as progress toward a final dichotomy, not as its completion.Source: §1 · pp. 4–5

2 Preliminaries

The preliminaries establish the matrix and gadget framework used for planar graph-homomorphism reductions. Thickening and stretching gadgets support interpolation, while the Potts model supplies a hardness source.

2 Preliminaries

  • Scaling a symmetric matrix by a nonzero constant leaves the planar graph-homomorphism problem polynomial-time Turing equivalent.The preliminaries consider real-valued symmetric matrices, including full-rank and positive-definite subsets.Source: §2 · p. 5

2.1 Thickening Gadgets

  • A planar edge gadget replaces each input edge with a planar graph fragment whose symmetric signature defines the resulting reduction.Thickening uses two labeled vertices connected by parallel edges; replacing every edge yields a planar instance.Source: §2 · p. 5, §2.1 · p. 5
  • Thickening and gadget interpolation use oracle evaluations at several parameters to recover partition functions for more general matrices.The method forms and solves a Vandermonde system; thickening also supports entrywise-power matrices and signed-monomial parameterizations.Source: §2.1 · p. 6

2.2 Stretching Gadgets

  • Stretching replaces an edge with a path, and its matrix powers likewise permit interpolation to other matrices.The method evaluates path lengths, forms a Vandermonde system, and uses the eigendecomposition to define a real-parameter matrix family.Source: §2.2 · pp. 6–7

2.3 Hardness Source

  • The q-state Potts model is a planar #P-hardness source for q ≥ 3 when its nonnegative parameter x differs from 1.At x = 0, the problem counts q-colorings of planar graphs; the Potts spectral lattice is specified by integer vectors whose entries sum to zero and whose first entry is zero.Source: §2.3 · p. 7

3 Hardness Criteria

The paper gives spectral and determinant criteria for proving planar graph-homomorphism hardness despite quantum symmetries. The spectral criterion applies to a rank-one perturbation, while the determinant criterion uses the log-entry matrix.

3 Hardness Criteria

  • Both criteria prove hardness even when M has nontrivial quantum symmetry, reducing from the Potts model.The spectral route uses stretching and thickening; the determinant criterion applies the spectral result with matrix perturbation theory.Source: §3 · p. 8

3.1 Spectral Criterion

  • For q ≥ 3, a positive vector u makes Pl-GH(I + uuT) #P-hard, establishing the rank-one hardness result used by the spectral criterion.The proof stretches the matrix to separate generating sets for diagonal and off-diagonal entries, then reduces from q-vertex coloring.Source: §3.1 · p. 8
  • If the eigenvalue lattice of M is contained in the Potts eigenvalue lattice, then Pl-GH(M) is #P-hard.The criterion transfers hardness from I + uuT using the Perron eigenvector.Source: §3.1 · p. 8

3.2 Determinant Criterion

  • For q ≥ 3, the determinant condition on the log-entry matrix L and all-one vector implies that Pl-GH(M) is #P-hard.The proof analyzes eigenvalue branches of a perturbed matrix near the zero eigenvalue of the all-one matrix.Source: §3.2 · p. 10

4 Circulant Matrix of Prime Order

For prime q ≥ 3, the paper proves planar graph-homomorphism problems defined by positive definite circulant matrices are #P-hard. The proof uses θ-stretching to bring their spectral lattice within the Potts lattice.

4 Circulant Matrix of Prime Order

  • For sufficiently large θ, θ-stretching yields a matrix whose spectral lattice is contained in the Potts lattice.The argument uses an asymptotic analysis of eigenvalues and a cyclotomic property specific to prime q ≥ 3.Source: §4 · p. 10
  • A circulant matrix is formed by cyclically shifting each row from the row above.The matrix is specified by its first row, C(c0, c1, …, cq−1).Source: §4 · p. 10
  • Every positive definite circulant matrix of prime order q ≥ 3 defines a #P-hard planar graph-homomorphism problem.The proof establishes the result by reducing from the Potts model of the same size.Source: §4 · pp. 10–11

5 Tensor Product of 2 by 2 Matrices

For tensor products of 2 × 2 matrices, the paper gives a hardness-versus-tractability classification based on the factors’ diagonal entries. A reduced spectral-lattice criterion supplies a route to hardness.

5 Tensor Product of 2 by 2 Matrices

  • For a tensor product M of 2×2 real factors Ai, Pl-GH(M) is #P-hard unless every factor has equal diagonal entries; then each is a matchgate and holographic reduction to FKT gives P-time tractability.Source: §5 · p. 11
  • If the reduced spectral lattice generated by the factors’ spectral radii is trivial, then Pl-GH(M) is #P-hard.The paper extends the spectral hardness criterion to tensor products of 2 × 2 matrices.Source: §5 · pp. 13–14
  • For nonnegative symmetric factors, hardness holds unless each factor with nonzero off-diagonal entry and nonzero determinant has equal diagonal entries; that case is polynomial-time computable.The condition is restricted to the index set I of factors specified in Theorem 5.Source: §5 · p. 14

A A Very Brief Introduction to Quantum Automorphism Groups and the “Quantum Barrier”

Quantum automorphism groups explain why planar edge gadgets may fail to separate matrix labels, even when classical symmetries do not. The paper develops a spectral criterion that can prove hardness without breaking those symmetries, while noting that the criterion is sufficient but not necessary.

Quantum barrier

  • When labels share a Qut(M) orbit, every planar edge gadget has equal diagonal entries on those labels, preventing vertex separation.This barrier can occur even when the classical automorphism group is trivial.Source: A A Very Brief Introduction to Quantum… · p. 16

Beyond vertex separation

  • For circulant matrices, all labels lie in one quantum orbit, yet spectral arguments still yield reductions from same-sized hard problems.The quantum barrier rules out reductions from smaller domains, not every route to hardness.Source: A A Very Brief Introduction to Quantum… · p. 16

Potts-model regime

  • The maximal quantum automorphism group occurs precisely for matrices in the real span of the identity and all-ones matrices, the Potts-model family.This regime motivates a hardness condition that works within quantum-symmetry constraints.Source: A A Very Brief Introduction to Quantum… · p. 16

Spectral criterion

  • The spectral criterion certifies hardness when a planar gadget's eigenvalue-relation lattice is contained in the Potts-model lattice.It is checkable and applies even with nontrivial, including maximal, quantum symmetry.Source: A A Very Brief Introduction to Quantum… · pp. 16–17

Limits and tensor products

B Model of Computation

The paper formalizes planar graph-homomorphism computation for arbitrary real-valued matrices using a Turing-machine model. It reduces computation of the partition function to recovering polynomially many integer coefficients, while explicitly noting that the real-number treatment can be nonconstructive.

Real-valued matrices

  • For arbitrary real matrices, the formal model assumes a field representation that may require nonconstructive information about transcendental entries.A polynomial-time reduction then establishes a logical implication between algorithms, not a constructive algorithm.Source: B Model of Computation · pp. 17–19

COUNT(M)

  • For fixed matrix M, COUNT(M) asks for the number of labelings whose edge-weight product equals a specified field element.The partition function is expressed by grouping terms with the same product value.Source: B Model of Computation · p. 18

Coefficient recovery

  • Only polynomially many distinct edge-weight products occur, and querying the partition function on thickened graphs yields a full-rank Vandermonde system for their counts.Solving the system recovers the integer coefficients in polynomial time.Source: B Model of Computation · pp. 18–19

C Planar Edge Gadgets

Scaling a matrix by any nonzero real constant preserves the planar graph-homomorphism problem up to polynomial-time Turing equivalence.

Matrix scaling

  • For any nonzero real c, oracle access to Pl-GH(M) or Pl-GH(cM) gives oracle access to the other.Thus the two problems are polynomial-time Turing equivalent.Source: C Planar Edge Gadgets · p. 19

C.1 Thickening Gadgets

Thickening gadgets and interpolation let the authors transform a matrix's entries and reduce the resulting planar homomorphism problems to the original one. The proof recovers product-weight counts by Vandermonde interpolation.

Generating sets

  • Every finite set of nonzero real entries has a generating set represented by unique signs and integer powers of generators greater than one.For a fixed generating set, each matrix entry has a unique such representation.Source: §C.1 · p. 20

Thickening and interpolation

  • For an entry-generating set, planar homomorphism problems for matrices N parameterized by z reduce to Pl-GH(M).The reduction computes the transformed partition function from product-weight counts recovered using a full-rank Vandermonde system.Source: §C.1 · pp. 20–22

Coefficient recovery

  • The multiplicities of distinct edge-weight products can be recovered in polynomial time because the associated Vandermonde system has full rank.The product-value set has polynomial size in the number of edges.Source: §C.1 · p. 21

Thickening transformations

  • Thickening transformations T(M; z) reduce to Pl-GH(M) for every real parameter vector z.The stated reduction applies to matrices with nonzero entries and a generating set for those entries.Source: §C.1 · p. 22

C.2 Stretching Gadgets

The section establishes reductions between planar graph homomorphism problems using spectral stretching and lattice interpolation. These reductions transfer tractability or hardness from a transformed matrix to the original matrix.

C.2 Stretching Gadgets

  • If M = HDH^T, then Pl-GH(HΔH^T) reduces to Pl-GH(M) when the eigenvalue lattice of M is contained in the lattice of the nonzero diagonal entries of Δ.The stated containment is L(λ1, …, λq) ⊆ L(Δ1, …, Δq).Source: §C.2 · p. 23
  • The spectral stretch SM(θ) is defined by raising M’s positive eigenvalues to the power θ while retaining its eigenvectors.The definition is independent of the chosen orthogonal decomposition of M.Source: §C.2 · p. 24

D Hardness Criteria

Lemma 8 constructs disjoint multiplicatively generating sets for the diagonal and off-diagonal entries of cI + uu^T. Their union generates every entry of the matrix.

D Hardness Criteria

  • For q ≥ 3 and positive u, some c > 0 makes the diagonal and off-diagonal entries of cI + uu^T have disjoint generating sets whose union generates all its entries.The construction uses multiplicative independence between generators for off-diagonal products uiuj and the distinct values ui.Source: D Hardness Criteria · pp. 24–25
  • The off-diagonal generators can be chosen multiplicatively independent before c is introduced.The proof selects generators for the products uiuj with no nontrivial integer relation among them.Source: D Hardness Criteria · p. 25
  • Choosing c transcendental over the field generated by the off-diagonal and distinct coordinate values establishes the required multiplicative independence.The proof rules out a nontrivial multiplicative relation by forming a nonzero polynomial that cannot vanish at transcendental c.Source: D Hardness Criteria · p. 25

E Circulant Matrix of Prime Order

The section analyzes eigenvalues of positive definite circulant matrices and applies the resulting spectral relations to Potts matrices. For q ≥ 3, the cited result establishes hardness for Potts matrices whenever x differs from 1.

E Circulant Matrix of Prime Order

F Tensor Product of 2 by 2 Matrices

The section classifies planar graph homomorphism problems for tensor products of 2 by 2 matrices through diagonal-entry conditions and spectral hardness criteria. Equal-diagonal factors yield tractability, while the stated conditions identify when the problem is #P-hard.

F Tensor Product of 2 by 2 Matrices

  • For positive definite positive factors, equal diagonals give matchgate-transformable signatures, while distinct diagonals reduce the hardness proof to the non-matchgate case.The proof normalizes and stretches factors into the regime 1 > bi > ci > bi^2 > 0 before applying the hardness criterion.Source: F Tensor Product of 2 by 2 Matrices · pp. 28, 30
  • If the multiplicative relation lattice of the spectral ratios ρ(Bi) is trivial, Lemma 19 gives #P-hardness.The proof uses stretching to obtain distinct ratios, then applies the criterion to the tensor product.Source: F Tensor Product of 2 by 2 Matrices · pp. 28–30
  • When a factor has zero determinant, it is rank one; the determinant-based theorem excludes such factors from the index set I.The theorem’s condition tests only factors with both nonzero off-diagonal entry and nonzero determinant.Source: F Tensor Product of 2 by 2 Matrices · pp. 30–31
  • A zero off-diagonal factor splits M into two scaled direct-sum blocks, and the direct-sum result transfers their tractability or hardness to M.The blocks are αM′ and βM′.Source: F Tensor Product of 2 by 2 Matrices · p. 31
  • For nonzero M = ⊗Ai with nonnegative symmetric 2 by 2 factors, Pl-GH(M) is #P-hard unless every factor with nonzero off-diagonal and nonzero determinant has equal diagonal entries; otherwise it is computable in P-time.The criterion applies to factors indexed by I = {i : (Ai)12 ≠ 0 and det(Ai) ≠ 0}.Source: F Tensor Product of 2 by 2 Matrices · p. 31
Loading 2609.36072v1…