  Background: A classical problem in metabolic design is to maximize the
production of desired compound in a given chemical reaction network by
appropriately directing the mass flow through the network. Computationally,
this problem is addressed as a linear optimization problem over the "flux
cone". The prior construction of the flux cone is computationally expensive and
no polynomial-time algorithms are known. Results: Here we show that the output
maximization problem in chemical reaction networks is NP-complete. This
statement remains true even if all reactions are monomolecular or bimolecular
and if only a single molecular species is used as influx. As a corollary we
show, furthermore, that the detection of autocatalytic species, i.e., types
that can only be produced from the influx material when they are present in the
initial reaction mixture, is an NP-complete computational problem. Conclusions:
Hardness results on combinatorial problems and optimization problems are
important to guide the development of computational tools for the analysis of
metabolic networks in particular and chemical reaction networks in general. Our
results indicate that efficient heuristics and approximate algorithms need to
be employed for the analysis of large chemical networks since even conceptually
simple flow problems are provably intractable.
