Characterization and computation of ancestors in reaction systems

In reaction systems, preimages andnth ancestors are sets of reactants leading to the production of a target set of products in either 1 ornsteps, respectively. Many computational problems on preimages and ancestors, such as finding all minimum-cardinalitynth ancestors, computing their size or counting them, are intractable. In this paper, we characterize allnth ancestors using a Boolean formula that can be computed in polynomial time. Once simplified, this formula can be exploited to easily solve all preimage and ancestor problems. This allows us to directly relate the difficulty of ancestor problems to the cost of the simplification so that new insights into computational complexity investigations can be achieved. In particular, we focus on two problems: (i) deciding whether a preimage/nth ancestor exists and (ii) finding a preimage/nth ancestor of minimal size. Our approach is constructive, it aims at finding classes of reactions systems for which the ancestor problems can be solved in polynomial time, in exact or approximate way.

Automated summary

This paper characterizes all nth ancestors using a Boolean formula that can be computed in polynomial time, providing new insights into computational complexity investigations. The focus is on determining the existence of a preimage/nth ancestor and finding a preimage/nth ancestor of minimal size, with an aim to solve ancestor problems in polynomial time, in exact or approximate way.