2022/03/21 by Julio Aracena, Aracena, Julio, Florian Bridoux +5
Computer Science · Biochemistry, Genetics and Molecular Biology · #Interconnection Networks and Systems #Formal Methods in Verification #Gene Regulatory Network Analysis
paper · pdf · doi:10.48550/arxiv.2203.11361
In this paper, we deal the following decision problem: given a conjunctive Boolean network defined by its interaction digraph, does it have a limit cycle of a given length k? We prove that this problem is NP-complete in general if k is a parameter of the problem and in P if the interaction digraph is strongly connected. The case where k is a constant, but the interaction digraph is not strongly connected remains open. Furthermore, we study the variation of the decision problem: given a conjunctive Boolean network, does there exist a block-sequential (resp. sequential) update schedule such that there exists a limit cycle of length k? We prove that this problem is NP-complete for any constant k >= 2.