Zeros of Holant Problems

Abstract

We present fully polynomial-time (deterministic or randomised) approximation schemes for Holant problems, defined by a non-negative constraint function satisfying a generalised second-order recurrence modulo in a couple of exceptional cases. As a consequence, any non-negative Holant problem on cubic graphs has an efficient approximation algorithm unless the problem is equivalent to approximately counting perfect matchings, a central open problem in the area. This is in sharp contrast to the computational phase transition shown by two-state spin systems on cubic graphs. Our main technique is the recently established connection between zeros of graph polynomials and approximate counting.

Topics & Concepts