Polynomial-time controllability analysis of Boolean networks

This paper discusses the controllability problem of Boolean networks with inputs (control nodes) and outputs (controlled nodes). An algorithm for testing controllability is in general NP-hard, and the existing polynomial-time algorithm is limited to a class of tree-structure networks. In this paper, based on a sufficient condition for controllability, a polynomial-time algorithm is proposed. The proposed algorithm is applicable to a wider class of large-scale Boolean networks compared with the existing algorithm. The key idea in our approach is to use an adjacency matrix of a directed graph induced by a Boolean network, and Boolean operations are not focused. The effectiveness of the proposed approach is shown by an example of a biological network.