Improvement of biological strains through targeted modification of metabolism is essential for successful development of bioprocesses. The computational complexity of optimization procedures routinely used for identifying genetic targets limits their application to genome-scale metabolic networks. In this study, we combined graph theoretic approaches with mixed-integer liner programming (MILP) to reduce the search space and thus reducing computational time. Specifically, we used cut-sets (minimal set of reactions that cuts metabolic networks) as additional constraints to reduce the search space. The efficacy of proposed approach is illustrated by identifying minimal reaction set for Saccharomyces Cerevisiae. © 2009 Elsevier B.V. All rights reserved.