Approximating the volume of a truncated relaxation of the independence polytope

Bencs, Ferenc; Regts, Guus

doi:10.1007/s00454-026-00824-y

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.

Additional Metadata
Keywords	Deterministic volume computation, Independence polytope, Interpolation method
Persistent URL	doi.org/10.1007/s00454-026-00824-y
Journal	Discrete and Computational Geometry
Rights	creativecommons.org/licenses/by/4.0/
Organisation	Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands
Citation APA Style AAA Style APA Style Cell Style Chicago Style Harvard Style IEEE Style MLA Style Nature Style Vancouver Style American-Institute-of-Physics Style Council-of-Science-Editors Style BibTex Format Endnote Format RIS Format CSL Format DOIs only Format	Bencs, F., & Regts, G. (2026). Approximating the volume of a truncated relaxation of the independence polytope. Discrete and Computational Geometry. doi:10.1007/s00454-026-00824-y