the kostka semigroup consists of pairs of partitions with at most r parts that have a 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 recent speculation of p. belkale concerning the semigroup controlling nonvanishing conformal blocks.