Minimal Controllability of Conjunctive Boolean Networks is NP-Complete
This work establishes the computational complexity of a fundamental control problem for Boolean networks, which is relevant to systems biology and network control.
The paper proves that finding the minimal set of state-variables to control in a conjunctive Boolean network to achieve controllability is NP-complete, despite providing a polynomial-time algorithm for testing controllability.
Given a conjunctive Boolean network (CBN) with $n$ state-variables, we consider the problem of finding a minimal set of state-variables to directly affect with an input so that the resulting conjunctive Boolean control network (CBCN) is controllable. We give a necessary and sufficient condition for controllability of a CBCN; an $O(n^2)$-time algorithm for testing controllability; and prove that nonetheless the minimal controllability problem for CBNs is NP-hard.