Strong Structural Controllability of Boolean Networks: Polynomial-Time Criteria, Minimal Node Control, and Distributed Pinning Strategies

In this article, we initiate the strong structural controllability of Boolean networks (BNs), in order to cope with the difficulty of identifying intricate nodal dynamics. The derived necessary and sufficient criteria for the strong structural controllability of BNs are checkable in a polynomial amount of time. As an interesting feature, controllability is shown to be equivalent to fixed-time controllability in the network-structure regard. We further explore the minimal strong structural controllability problem of BNs that, reduced from the minimum vertex cover problem of graphs, consequently turns out to be NP-hard. More worthy implications are that our results on the strong structural controllability also serve as the basis to improve several existing approaches to a certain extent. First, the network aggregation subject to the controllability of BNs is provided where the aggregated blocks, except the rooted blocks, are strongly structurally controllable. Second, the pinning controllers are carried out to render an arbitrary BN controllable through node-to-node message exchange in a distributed form while traditional results only check the controllability of BNs with the preassigned controllers. Notably, the time complexity to design such controllers reduces to be only exponential with the maximal in-degree of pinned nodes rather than the node number of networks. As for the stochastic counterpart, upon the equivalence between the asymptotic stability of stochastic BNs and the criteria of strong structural controllability, we also further facilitate the design of distributed controllers to asymptotically stabilize stochastic BNs in probability.