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...
Kaydedildi:
| Asıl Yazarlar: | , |
|---|---|
| Materyal Türü: | Makale |
| Baskı/Yayın Bilgisi: |
2026
|
| Konular: | |
| Online Erişim: | https://arxiv.org/abs/2610.05412 http://arxiv.org/abs/2610.05412 |
| Etiketler: |
Etiket eklenmemiş, İlk siz ekleyin!
|