Skip to main content

Inapproximability of the independent set polynomial in the complex plane

Andreas Galanis ( University of Oxford )

Abstract:
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 Δ? 
This problem is already well understood when λ is a real number using connections 
to phase transitions in statistical physics on the Δ-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 Δ-regular tree 
for general complex values of λ. They identified a region Λ(Δ) in the complex plane and, 
motivated by the real case, they asked whether Λ(Δ) marks the approximability threshold 
for general complex values λ.
 
We show that for every λ outside of Λ(Δ), the problem of approximating p_G(λ) on graphs G 
with max degree Δ 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.

 

 

Share this: