Matching Algorithms of Minimum Input Selection for Structural Controllability Based on Semi-Tensor Product of Matrices

In 2011, Liu, et al. investigated the structural controllability of directed networks. They proved that the minimum number of input signals, driver nodes, can be determined by seeking a maximum matching in the directed network. Thus, the algorithm for seeking a maximum matching is the key to solving the structural controllability problem of directed networks. In this study, the authors provide algebraic expressions for matchings and maximum matchings proposed by Liu, et al. (2011) via a new matrix product called semi-tensor product, based on which the corresponding algorithms are established to seek matchings and maximum matchings in digraphs, which make determining the number of driver nodes tractable in computer. In addition, according to the proposed algorithm, the authors also construct an algorithm to distinguish critical arcs, redundant arcs and ordinary arcs of the directed network, which plays an important role in studying the robust control problem. An example of a small network from Liu’s paper is used for algorithm verification.