A computational procedure for identifying the minimal set of metabolic reactions capable of supporting various growth rates on different substrates is introduced and applied to a flux balance model of the Escherichia coli metabolic network. This task is posed mathematically as a generalized network optimization problem. The minimal reaction sets capable of supporting specified growth rates are determined for two different uptake conditions: (i) limiting the uptake of organic material to a single organic component (e.g., glucose or acetate) and (ii) allowing the importation of any metabolite with available cellular transport reactions. We find that minimal reaction network sets are highly dependent on the uptake environment and the growth requirements imposed on the network. Specifically, we predict that the E. coli network, as described by the flux balance model, requires 224 metabolic reactions to support growth on a glucose-only medium and 229 for an acetate-only medium, while only 122 reactions enable growth on a specially engineered growth medium.