Abstract
We study the problem of approximating 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 has an FPRAS on general graphs. For general complex values of $\gamma$, Patel and Regts, building on methods developed by Barvinok, showed that the problem has 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 result completes the picture for the approximability of the matching polynomial on bounded degree graphs. We show that for all $\Delta\geq 3$ 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 the extent to which 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. Joint work with Ivona Bezakova, Andreas Galanis, and Daniel Stefankovic.