On Constrained Input Selections for Structured Systems: Polynomially Solvable Cases

This paper investigates two related optimal input selection problems for structured systems. Given are an autonomous system and a set of inputs, where whether an input can directly actuate a state variable is given a priori, and each input has a non-negative cost. The problems are, selecting the minimum cost of inputs, and selecting the inputs with the smallest possible cost with a bound on their cardinality, all to ensure system structural controllability. Those problems are known to be NP-hard in general. In this paper, instead of finding approximation algorithms, we explore classes of systems on which those problems are polynomially solvable. We show subject to the so-called source strongly-connected component separated input constraint, which contains all the currently known nontrivial polynomially solvable cases as special ones, those problems can be solvable in polynomial time. We do this by first formulating those problems as equivalent integer linear programmings (ILPs), and then proving that the corresponding constraint matrices are totally unimodular. This property allows us to solve those ILPs efficiently simply via their linear programming (LP) relaxations, leading to a unifying algebraic method for these problems with polynomial time complexity. A numerical example is given to illustrate these results.