Parametric Polyhedra with at least k Lattice Points: Their Semigroup Structure and the k-Frobenius Problem

The well-studied semigroup Sg(A) = {b : b = Ax; x in Z^n; x >= 0} can be
stratified by the sizes of the polyhedral fibers IPA(b) = {x : Ax = b; x >= 0; x in Z^n}. The
key theme of this paper is a structure theory that characterizes precisely the set Sg_k(A) of
all vectors b in Sg(A) such that their fiber IPA(b) has at least k-solutions. We demonstrate
that this set is finitely generated, a union of translated copies of a semigroup which can be
computed explicitly via Hilbert bases computations. Related results can be derived for those
right-hand-side vectors b for which IPA(b) has exactly k solutions or fewer than k solutions.
We also show that, when n, k are fixed natural numbers, one can compute in polynomial time
an encoding of Sg_k(A) as a generating function, using a short sum of rational functions.
As a consequence, one can identify all right-hand-side vectors that have at least k solutions.
Using this tool we prove that for fixed n; k the k-Frobenius number can be computed in
polynomial time, generalizing a well-known result of R. Kannan.