Minimum Input Selection for Structural Controllability
For control theorists, this solves a key combinatorial problem in structural controllability with an efficient algorithm.
The paper presents a deterministic algorithm that finds the minimum set of state variables to make a linear system structurally controllable, avoiding forbidden variables, in O(n + m√n) time.
Given a linear system $\dot{x} = Ax$, where $A$ is an $n \times n$ matrix with $m$ nonzero entries, we consider the problem of finding the smallest set of state variables to affect with an input so that the resulting system is structurally controllable. We further assume we are given a set of "forbidden state variables" $F$ which cannot be affected with an input and which we have to avoid in our selection. Our main result is that this problem can be solved deterministically in $O(n+m \sqrt{n})$ operations.