Complete enumeration of irreducible autocatalytic sets with bounded supplier choice
Abstract
An irreducible reflexively autocatalytic and food-generated set (irreducible RAF, or irrRAF) is an inclusion-minimal nonempty RAF of a finite catalytic reaction system. A companion classification shows that no uniform output-polynomial algorithm lists the complete family of irrRAFs unless , so unconditional tractability must come from structure in the input. We identify such structure in the multiplicity of suppliers. After polynomial maximal-RAF pruning, let be the number of reactions producing a nonfood species and let be the number of effective catalyst alternatives of a reaction (one, when a food catalyst is available). The supplier excess is computed from the input and bounds the number of deterministic supplier resolutions. We prove that every irrRAF survives at least one resolution, chosen by a globally shared earliest-producer rule; that the irrRAFs of a pruned resolution are exactly the sink strongly connected components of its consumer-to-supplier dependency graph; and that validating each such component in the original system, with one maximal-RAF call per reaction, yields precisely the complete original family. The algorithm runs in time and space for explicit input length ; it places no bound on the length of food-generation chains, so arbitrarily large deterministic systems have . Because the components of one resolution are disjoint, every reaction lies in at most irrRAFs and the total output length is at most for a maximal RAF of reactions; a coupled gate family shows that both bounds are attained up to a constant factor. Deleting reactions filters the family exactly and cannot increase ; incidence-separated components let the parameter be replaced by its largest local value, giving fixed-parameter tractability in ; and destructive reaction sets are exactly the transversals of the catalogue, which yields a -approximate greedy intervention and exact cut-cost, cut-count and reliability formulas at zero excess. The catalogue theorem, its candidate bounds, the overlap bounds and the restriction identity are machine-checked in Lean 4; the cost, component and intervention results have conventional proofs. Bounded exact tests and an instrumented implementation illustrate the mechanisms.