Paper detail

Complexity of limit-cycle problems in Boolean networks

Boolean networks are a general model of interacting entities, with applications to biological phenomena such as gene regulation. Attractors play a central role, and the schedule of entities update is a priori unknown. This article presents results on the computational complexity of problems related to the existence of update schedules such that some limit-cycle lengths are possible or not. We first prove that given a Boolean network updated in parallel, knowing whether it has at least one limit-cycle of length $k$ is $\text{NP}$-complete. Adding an existential quantification on the block-sequential update schedule does not change the complexity class of the problem, but the following alternation brings us one level above in the polynomial hierarchy: given a Boolean network, knowing whether there exists a block-sequential update schedule such that it has no limit-cycle of length $k$ is $Σ_2^\text{P}$-complete.