A reaction cut is a set of chemical reactions whose deletion blocks the operation of given reactions or the production of given chemical compounds. In this paper, we study two problems Reaction-Cut and MD-ReactionCut for calculating the minimum reaction cut of a metabolic network under a Boolean model. These problems are based on the flux balance model and the minimal damage model respectively. We show that ReactionCut and MD-ReactionCut are NP-hard even if the maximum outdegree of reaction nodes (K out) is one. We also present O(1.822n), O(1.959 n) and o(2 n) time algorithms for MD-ReactionCut with K out = 2,3, k respectively where n is the number of reaction nodes and k is a constant. The same algorithms also work for ReactionCut if there is no directed cycle. Furthermore, we present a 2 O((logn)√n) time algorithm, which is faster than O((1 + ε) n) for any positive constant ε, for the planar case of MD-ReactionCut under a reasonable constraint utilizing Lipton and Tarjan's separator algorithm. Copyright © 2010 The Institute of Electronics,.