Complexity of limit cycles with block-sequential update schedules in conjunctive networks

03/21/2022
by   Julio Aracena, et al.
0

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.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset