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 : A x = 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 ( poly ( n , m , ‖ y ‖ ∞ ) ( ‖ y ‖ ∞ + 1 ) n ) time and O ( poly ( n , m , ‖ y ‖ ∞ ) ) space. This improves, in terms of space complexity, a naive DP algorithm with O ( ( ‖ y ‖ ∞ + 1 ) n ) -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 ( poly ( n , m , ‖ b ‖ ∞ ) ( ‖ b ‖ ∞ + 1 ) ( 1 − 1 / k ) n ) 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.