Minimal structural perturbations for controllability of a networked system: Complexities and approximations

Link additions/deletions and actuator/sensor failures are common structural perturbations for real networked systems. In this paper, we consider three related problems on determining the minimal cost structural perturbations, including link additions, link deletions, and input deletions to make a networked system structurally controllable/uncontrollable, mainly focusing on their computational complexities and approximations. Formally, given a structured system, it is proven that (i) it is NP-hard to add the minimal cost of links, including links among state variables (ie, state links) and links from the existing inputs to state variables (ie, input links), from a given set of links to make the system structurally controllable; (ii) it is NP-hard to determine the minimal cost of links whose deletions deteriorate structural controllability of the system, even when the removable links are restricted in either the input links or the state links. It is also proven that determining the minimal cost of inputs whose deletions cause structural uncontrollability is strongly NP-hard even with dedicated input structure. Furthermore, some fundamental approximation results for these problems are established. These results may serve an answer to the general hardness and approximability of optimally designing (modifying) a structurally controllable network topology and of measuring controllability robustness against link/input failures. Additionally, several polynomial-time tractable cases of the aforementioned problems are also identified.