Self-generating autocatalytic networks: structural results, algorithms, and their relevance to evolutionary processes

The concept of an autocatalytic network of reactions that can form and persist, starting from just an available food source, has been formalised by the notion of a Reflexively-Autocatalytic and Food generated (RAF) set. The theory and algorithmic results concerning RAFs have been applied to a range of settings, from metabolic questions arising at the origin of life, to ecological networks, and cognitive models in cultural evolution. In this paper, we present new structural and algorithmic results concerning RAF sets, by studying more complex modes of catalysis that allow certain reactions to require multiple catalysts (or to not require catalysis at all), and discuss the differing ways catalysis has been viewed in the literature. We then focus on the structure and analysis of minimal RAFs, and derive structural results and polynomial-time algorithms, with applications to metabolic network data described briefly.