Parameterized Complexity of Inverse Scope Problems in Metabolic Networks

Inverse Scope Problem aims to determine, by analyzing the structure of a metabolic network, the minimum cardinality set of seed compounds required for the synthesis of a specific compound or set of compounds. This paper examines the computational complexity of three variants of the inverse scope problem from parameterized complexity view. With as natural parameter the minimum number of metabolites necessary for synthesizing a set of target metabolites, we prove that inverse scope problem with two forbidden sets is W[2]-hard. In addition, we point out that the inverse scope problem with no forbidden set and the inverse scope problem with a forbidden set are also W[2]-hard.