Minimal Controllability of Conjunctive Boolean Networks is NP-Complete

Abstract

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.

References in corpus (4)

• Genetic networks with canalyzing Boolean rules are always stable
• Identification of control targets in Boolean molecular network models via computational algebra
• Using synchronous Boolean networks to model several phenomena of collective behavior
• Stability Structures of Conjunctive Boolean Networks

Cited by in corpus (7)

• A Polynomial-Time Algorithm for Solving the Minimal Observability Problem in Conjunctive Boolean Networks
• Output Selection and Observer Design for Boolean Control Networks: A Sub-Optimal Polynomial-Complexity Algorithm
• Asymptotic Behavior of Conjunctive Boolean Networks Over Weakly Connected Digraphs
• Polynomial-Time Algorithms for Structurally Observable Graphs by Controlling Minimal Vertices
• A General Control Framework for Boolean Networks
• Categorization Problem on Controllability of Boolean Control Networks
• Pinning Stabilizer Design for Large-Scale Probabilistic Boolean Networks