Constraint-based approaches recently brought new insight into our understanding of metabolism. By making very simple assumptions such as that the system is at steady-state and some reactions are irreversible, and without requiring kinetic parameters, general properties of the system can be derived. A central concept in this methodology is the notion of an elementary mode (EM for short). The computation of EMs still constitutes a limiting step in metabolic studies and several algorithms have been proposed to address this problem leading to increasingly faster methods.

First results regarding network consistency will be presented. Most consistency problems can be solved in polynomial time (are easy). Then the complexity of finding and counting elementary modes is presented, showing in particular that finding one elementary mode is easy but that this task becomes hard when a specific EM i.e. an EM containing some specified reactions) is sought. Also a number of EM related problems will be considered.

Then models and results on a closely related task is presented: the computation of so-called minimal reaction cut sets. Also this problem is hard. Two positive results will be presented, which both allow to avoid computing EMs as a prior to the computation of reaction cuts. The first one is a polynomial time approximation algorithm for finding a minimum reaction cut set. The second one is a test for verifying if a set of reactions constitutes a reaction cut; this test could be readily included in existing algorithms to improve their performance. Finally, we discuss the complexity of other cut-related problems.

Joint work with Vincent Lacroix, Alberto Marchetti-Spaccamela, Marie-France Sagot and Flavio Chierichetti.