Approximating the Volume of a Truncated Relaxation of the Independence Polytope
Ferenc Bencs, Guus Regts · Discrete & Computational Geometry · 2026
Abstract Answering a question of Gamarnik and Smedira [15], 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.