Resilient Structural Stabilizability of Undirected Networks
For researchers in network control, this paper provides foundational results on structural stabilizability of undirected networks and addresses optimal attack and recovery problems, though the NP-hardness results and approximation algorithm are incremental contributions.
This paper derives a graph-theoretic condition for structural stabilizability of undirected networks and proposes a method to compute the maximum dimension of stabilizable subspace from topology. It shows that both optimal actuator-disabling attack and optimal recovery problems are NP-hard, and provides a (1-1/e) approximation algorithm for recovery.
In this paper, we consider the structural stabilizability problem of undirected networks. More specifically, we are tasked to infer the stabilizability of an undirected network from its underlying topology, where the undirected networks are modeled as continuous-time linear time-invariant (LTI) systems involving symmetric state matrices. Firstly, we derive a graph-theoretic necessary and sufficient condition for structural stabilizability of undirected networks. Then, we propose a method to infer the maximum dimension of stabilizable subspace solely based on the network structure. Based on these results, on one hand, we study the optimal actuator-disabling attack problem, i.e., removing a limited number of actuators to minimize the maximum dimension of stabilizable subspace. We show this problem is NP-hard. On the other hand, we study the optimal recovery problem with respect to the same kind of attacks, i.e., adding a limited number of new actuators such that the maximum dimension of stabilizable subspace is maximized. We prove the optimal recovery problem is also NP-hard, and we develop a (1-1/e) approximation algorithm to this problem.