A dichotomy for bounded degree graph homomorphisms with nonnegative weights
| Autor: | Govorov, Artem, Cai, Jin-Yi, Dyer, Martin |
|---|---|
| Rok vydání: | 2023 |
| Předmět: |
FOS: Computer and information sciences
Computer Science - Computational Complexity Computational Theory and Mathematics General Computer Science Computer Networks and Communications Applied Mathematics Counting problems Complexity dichotomy Theory of computation → Problems reductions and completeness Computer Science::Computational Complexity Computational Complexity (cs.CC) Graph homomorphism Theoretical Computer Science |
| Zdroj: | Journal of Computer and System Sciences. 132:1-15 |
| ISSN: | 0022-0000 |
| DOI: | 10.1016/j.jcss.2022.09.002 |
| Popis: | We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix A. Each symmetric matrix A defines a graph homomorphism function Z_A(⋅), also known as the partition function. Dyer and Greenhill [Martin E. Dyer and Catherine S. Greenhill, 2000] established a complexity dichotomy of Z_A(⋅) for symmetric {0, 1}-matrices A, and they further proved that its #P-hardness part also holds for bounded degree graphs. Bulatov and Grohe [Andrei Bulatov and Martin Grohe, 2005] extended the Dyer-Greenhill dichotomy to nonnegative symmetric matrices A. However, their hardness proof requires graphs of arbitrarily large degree, and whether the bounded degree part of the Dyer-Greenhill dichotomy can be extended has been an open problem for 15 years. We resolve this open problem and prove that for nonnegative symmetric A, either Z_A(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [Leslie A. Goldberg et al., 2010] for Z_A(⋅) also holds for simple graphs, where A is any real symmetric matrix. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect