Computational Complexity of Minimal Trap Spaces in Boolean Networks

Trap spaces of a Boolean network (BN) are the sub-hypercubes closed by the function of the BN. A trap space is minimal if it does not contain any smaller trap space. Minimal trap spaces have applications for the analysis of dynamic attractors of BNs with various update modes. This paper establishes computational complexity results of three decision problems related to minimal trap spaces of BNs: the decision of the trap space property of a sub-hypercube, the decision of its minimality, and the decision of the belonging of a given configuration to a minimal trap space. Under several cases on Boolean function specifications, we investigate the computational complexity of each problem. In the general case, we demonstrate that the trap space property is coNP-complete, and the minimality and the belonging properties are $\Pi_2^{\text P}$-complete. The complexities drop by one level in the polynomial hierarchy whenever the local functions of the BN are either unate, or are specified using truth-table, binary decision diagrams, or double-DNF (Petri net encoding): the trap space property can be decided in P, whereas the minimality and the belonging are coNP-complete. When the BN is given as its functional graph, all these problems can be decided by deterministic polynomial time algorithms.