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

In this paper, we deal with 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 is in P if the interaction digraph is strongly connected. The case where k is fixed, but the interaction digraph is not strongly connected, remains open. Furthermore, we study some variations of the decision problem: given a conjunctive Boolean network, does there exist a block-sequential (resp. sequential) update schedule such that there is a limit cycle of length k? We prove that these problems are NP-complete for any fixed constant k≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k \ge 2$$\end{document}.