The complexity of approximating the matching polynomial in the complex plane

Understand

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.