Abstract

Boolean networks have been used as models of gene regulation networks and other biological systems. One key element in these models is the update schedule, which indicates the order in which states are to be updated. The presence of any limit cycle in the dynamics of a network depends on the update scheme used. Here, we study the complexity of the problems of determining the existence of a block-sequential update schedule for a given Boolean network such that it yields any limit cycle (LCE) and does not yield any limit cycle (LCNE). Besides, we prove that in AND-OR networks LCE is NP-hard and LCNE is coNP-hard. Finally, we show that both problems are polynomial in symmetric AND-OR networks. For these networks, we find a polynomial characterization for the existence of limit cycles in terms of the interaction digraph.