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. © 2009 Elsevier Ireland Ltd.
Acuna, V., Marchetti-Spaccamela, A., Sagot, M-F., & Stougie, L. (2010). A note on the complexity of finding and enumerating elementary modes. BioSystems, 99, 210-214. https://doi.org/10.1016/j.biosystems.2009.11.004