A note on the complexity of finding and enumerating elementary modes.
In the context of the study into elementary modes of metabolic networks, we prove two complexity results. Enumerating elementary modes containing a specific reaction is hard in an enumeration complexity sense. The decision problem if there exists an elementary mode containing two specific reactions is NP-complete. The complexity of enumerating all elementary modes remains open.
Acuña
Vicente
V
Université de Lyon, France. viacuna@biomserv.univ-lyon1.fr
Marchetti-Spaccamela
Alberto
A
Sagot
Marie-France
MF
Stougie
Leen
L
D053858:Metabolic Networks and Pathways / Q000502:physiology; D008954:Models, Biological