Preprint 2022-09
Julio Aracena, Florian Bridoux, Luis Gomez, Lilian Salinas:
Complexity of limit cycles with block-sequential update schedules in conjunctive networks
Abstract:
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. Keywords: Boolean network, limit cycle, update schedule, update digraph, NP-Hardness.
