On the complexity of the constrained input selection problem for structural linear systems

摘要: This paper studies the problem of, given structure of a linear-time invariant system and set possible inputs, finding smallest subset input vectors that ensures system's structural controllability. We refer to this as minimum constrained selection (minCIS) problem, since has be performed on an initial inputs. prove minCIS is NP-hard, which addresses recent open question whether there exist polynomial algorithms (in size plant matrices) solve problem. To end, we show associated decision referred CIS, determining (of collection inputs) with prescribed cardinality exists controllability, NP-complete. Further, explore in detail practically important subclasses obtained by introducing more specific assumptions either dynamics or instances for systematic solution methods are provided constructing explicit reductions well known computational problems. The analytical findings illustrated through examples multi-agent leader-follower type control