Zeros and approximations of Holant polynomials on the complex plane
- We present fully polynomial time approximation schemes for a broad class of Holant problems with complex edge weights, which we call Holant polynomials. We transform these problems into partition functions of abstract combinatorial structures known as polymers in statistical physics. Our method involves establishing zero-free regions for the partition functions of polymer models and using the most significant terms of the cluster expansion to approximate them. Results of our technique include new approximation and sampling algorithms for a diverse class of Holant polynomials in the low-temperature regime (i.e. small external field) and approximation algorithms for general Holant problems with small signature weights. Additionally, we give randomised approximation and sampling algorithms with faster running times for more restrictive classes. Finally, we improve the known zero-free regions for a perfect matching polynomial.
Author details: | Katrin CaselORCiDGND, Philipp FischbeckORCiDGND, Tobias FriedrichORCiDGND, Andreas GöbelGND, Julius Albert Gregor LagodzinskiORCiDGND |
---|---|
DOI: | https://doi.org/10.1007/s00037-022-00226-5 |
ISSN: | 1016-3328 |
ISSN: | 1420-8954 |
Title of parent work (English): | Computational complexity : CC |
Publisher: | Springer |
Place of publishing: | Basel |
Publication type: | Article |
Language: | English |
Date of first publication: | 2022/07/27 |
Publication year: | 2022 |
Release date: | 2023/12/11 |
Tag: | Holant problems; approximate counting; graph; partition functions; polynomials |
Volume: | 31 |
Issue: | 2 |
Article number: | 11 |
Number of pages: | 52 |
Funding institution: | Projekt DEAL |
Organizational units: | Digital Engineering Fakultät / Hasso-Plattner-Institut für Digital Engineering GmbH |
DDC classification: | 0 Informatik, Informationswissenschaft, allgemeine Werke / 00 Informatik, Wissen, Systeme / 000 Informatik, Informationswissenschaft, allgemeine Werke |
Peer review: | Referiert |
Publishing method: | Open Access / Hybrid Open-Access |
License (German): | CC-BY - Namensnennung 4.0 International |