Abstract:
We give a deterministic polynomial-time approximation scheme ( FPTAS ) for the volume of the truncated fractional matching polytope for graphs of maximum degree Delta ,
where the truncation is by restricting each variable to the interval [ 0, ( 1 + delta ) / Delta ], and delta < = C / Delta for some constant C > 0.
We also generalise our result to the fractional matching polytope for hypergraphs of maximum degree Delta and maximum hyperedge size k, truncated by [ 0, ( 1 + delta ) / Delta ] as well,
where delta < = C * Delta ^ { -( 2k - 3) / (k - 1) } * 1 / k for some constant C > 0.
The latter result generalises both the first result for graphs ( when k = 2 ), and a result by Bencs and Regts (2024) for the truncated independence polytope ( when Delta = 2 ).
Our approach is based on the cluster expansion technique.
The full version of the paper is available here.