  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. In an appendix, the second and third
authors show that a natural extension of our main result on the Kostka
semigroup cannot be extended to the Littlewood-Richardson semigroup. This
furthermore gives a counterexample to a recent speculation of P. Belkale
concerning the semigroup controlling nonvanishing conformal blocks.
