The Complexity of Approximating the Matching Polynomial in the Complex Plane

DOI10.1145/3448645MaRDI QIDQ5065635zbMATHOpenAlexFDO

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

Publication date 22 March 2022

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

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

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)

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.

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; zbMATH DE number 69493
• scientific article; zbMATH DE number 4070302
• scientific article; zbMATH DE number 2151192
• On the Complexity of the Interlace Polynomial

Cited in

(7)

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

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)