Counting Integral Points in Polytopes via Numerical Analysis of Contour Integration

In this paper, we address the problem of counting integer points in a rational polytope described by P(y) = {x ∈ R^m: Ax= y, x ≥ 0}, where A is an n × m integer matrix and y is an n-dimensional integer vector. We study the Z transformation approach initiated in works by Brion and Vergne, Beck, and Lasserre and Zeron from the numerical analysis point of view and obtain a new algorithm on this problem. If A is nonnegative, then the number of integer points in P(y) can be computed in $O\left(\mathrm{poly}\left(n,m,\mathrm{\Vert }\mathit{y}{\mathrm{\Vert }}_{\mathrm{\infty }}\right){\left(\mathrm{\Vert }\mathit{y}{\mathrm{\Vert }}_{\mathrm{\infty }}+1\right)}^n\right)$ time and $O\left(\mathrm{poly}\left(n,m,\mathrm{\Vert }\mathit{y}{\mathrm{\Vert }}_{\mathrm{\infty }}\right)\right)$ space. This improves, in terms of space complexity, a naive DP algorithm with $O\left({\left(\mathrm{\Vert }\mathit{y}{\mathrm{\Vert }}_{\mathrm{\infty }}+1\right)}^n\right)$-size dynamic programming table. Our result is based on the standard error analysis of the numerical contour integration for the inverse Z transform and establishes a new type of an inclusion-exclusion formula for integer points in P(y).

We apply our result to hypergraph b-matching and obtain a $O\left(\mathrm{poly}\left(n,m,\mathrm{\Vert }\mathit{b}{\mathrm{\Vert }}_{\mathrm{\infty }}\right){\left(\mathrm{\Vert }\mathit{b}{\mathrm{\Vert }}_{\mathrm{\infty }}+1\right)}^{\left(1-1/k\right)n}\right)$ time algorithm for counting b-matchings in a k-partite hypergraph with n vertices and m hyperedges. This result is viewed as a b-matching generalization of the classical result by Ryser for k = 2 and its multipartite extension by Björklund and Husfeldt.