  The Kostka semigroup consists of pairs of partitions with at most r parts
that have positive Kostka coefficient. For this semigroup, Hilbert basis
membership is an NP-complete problem. We introduce KGR graphs and conservative
subtrees, through the Gale-Ryser theorem on contingency tables, as a criterion
for membership. In our main application, we show that if a partition pair is in
the Hilbert basis then the partitions are at most r wide. We also classify the
extremal rays of the associated polyhedral cone; these rays correspond to a
(strict) subset of the Hilbert basis.
