A Dichotomy for Planar Graph Homomorphisms with Nonnegative Weights

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 clas...

Descripción completa

Detalles Bibliográficos

Autores principales:	Liu, Chenghua, Meng, Boning
Formato:	Artículo
Publicado:	2026
Materias:	Computational Complexity
Acceso en línea:	https://arxiv.org/abs/2610.05412 http://arxiv.org/abs/2610.05412
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!