The Complexity of Approximating the Matching Polynomial in the Complex Plane

DOI10.1145/3448645zbMATH Open1495.68163arXiv1807.04930OpenAlexW3155374999MaRDI QIDQ5065635FDOQ5065635

D. Štefankovič, Leslie Ann Goldberg, Andreas Galanis, Ivona Bezáková

Publication date: 22 March 2022

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Abstract: We study the problem of approximating the value of the matching polynomial on graphs with edge parameter $gamma$, where $gamma$ takes arbitrary values in the complex plane. When $gamma$ is a positive real, Jerrum and Sinclair showed that the problem admits an FPRAS on general graphs. For general complex values of $gamma$, Patel and Regts, building on methods developed by Barvinok, showed that the problem admits an FPTAS on graphs of maximum degree $Delta$ as long as $gamma$ is not a negative real number less than or equal to $-1/(4(Delta-1))$. Our first main result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all $Deltageq3$ and all real $gamma$ less than $-1/(4(Delta-1))$, the problem of approximating the value of the matching polynomial on graphs of maximum degree $Delta$ with edge parameter $gamma$ is #P-hard. We then explore whether the maximum degree parameter can be replaced by the connective constant. Sinclair et al. showed that for positive real $gamma$ it is possible to approximate the value of the matching polynomial using a correlation decay algorithm on graphs with bounded connective constant (and potentially unbounded maximum degree). We first show that this result does not extend in general in the complex plane; in particular, the problem is #P-hard on graphs with bounded connective constant for a dense set of $gamma$ values on the negative real axis. Nevertheless, we show that the result does extend for any complex value $gamma$ that does not lie on the negative real axis. Our analysis accounts for complex values of $gamma$ using geodesic distances in the complex plane in the metric defined by an appropriate density function.

Full work available at URL: https://arxiv.org/abs/1807.04930

Recommendations

• The complexity of approximating the matching polynomial in the complex plane
• On the complexity of a piecewise linear algorithm for approximating roots of complex polynomials
• The complexity of polynomial-time approximation
• On the cost of approximating all roots of a complex polynomial
• Polynomial approximations in the complex plane
• On the complexity of the computation of certain classes of polynomials of several variables
• scientific article
• scientific article
• scientific article; zbMATH DE number 2151192
• On the Complexity of the Interlace Polynomial

zbMATH Keywords

approximate countingmatchingsmonomer-dimer modelpartition functionsconnective constant

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph polynomials (05C31) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Cited In (5)

• Zeros and approximations of holant polynomials on the complex plane
• The complexity of approximating the complex-valued Potts model
• Inapproximability of the independent set polynomial in the complex plane
• On the zeroes of hypergraph independence polynomials
• The Complexity of Approximating the Complex-Valued Ising Model on Bounded Degree Graphs

This page was built for publication: The Complexity of Approximating the Matching Polynomial in the Complex Plane

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5065635)