  Answering a question of Gamarnik and Smedira, we give a polynomial time
algorithm that approximately computes the volume of a truncation of a
relaxation of the independent set polytope, improving on their quasi-polynomial
time algorithm. Our algorithm is obtained by viewing the volume as an
evaluation of a graph polynomial and we approximate this evaluation using
Barvinok's interpolation method.
