LFCS Seminar: 24 April 2018 - Andreas Galanis

For a graph G, let p_G(λ) denote the independent set polynomial of G with parameter λ. For which λ can we approximate the value p_G(λ) on graphs G of maximum degree D? This problem is already well understood when λ is a real number using connections to phase transitions in statistical physics on the D-regular tree.  Understanding the case where λ is complex turns out to be more challenging.

Peters and Regts studied an analogue of the phase transition on the D-regular tree for general complex values of λ. They identified a region Λ(D) in the complex plane and, motivated by the real case, they asked whether Λ(D) marks the approximability threshold for general complex values λ.

 We show that for every λ outside of Λ(D), the problem of approximating p_G(λ) on graphs G with max degree D is indeed NP-hard. In fact, when λ is outside of the region and is not a positive real number, we give the stronger result that approximating p_G(λ) is actually #P-hard. 

 This is joint work with Ivona Bezakova, Leslie Ann Goldberg, and Daniel Stefankovic.