Approximate counting using Taylor’s theorem: a survey

Viresh Patel, Guus Regts, The Algorithmics Column by Thomas Erlebach


In this article we consider certain well-known polynomials associated with graphs including the independence polynomial and the chromatic polynomial. These polynomials count certain objects in graphs: independent sets in the case of the independence polynomial and proper colourings in the case of the chro- matic polynomial. They also have interpretations as partition functions in statistical physics.

The algorithmic problem of (approximately) computing these types of polyno- mials has been studied for close to 50 years, especially using Markov chain tech- niques. Around eight years ago, Barvinok devised a new algorithmic approach based on Taylor’s theorem for computing the permanent of certain matrices, and the approach has been applied to various graph polynomials since then. This arti- cle is intended as a gentle introduction to the approach as well as a partial survey of associated techniques and results.

Keywords: approximate counting, independence polynomial, complex zeros, chromatic polynomial.

Full Text:



  • There are currently no refbacks.