Reconstruction of Structural Controllability over Erdös-Rényi Graphs via Power Dominating Sets

Controllability, or informally the ability to force a system into a desired state in a finite time or number of steps, is a fundamental problem studied extensively in control systems theory with structural controllability recently gaining renewed interest. In distributed control systems, possible control relations are limited by the underlying network (graph) transmitting the control signals from a single controller or set of controllers. Attackers may seek to disrupt these relations or compromise intermediate nodes, thereby gaining partial or total control.

For a defender to re-gain full or partial control, it is therefore critical to rapidly reconstruct the control graph as far as possible. Failing to achieve this may allow the attacker to cause further disruptions, and may --- as in the case of electric power networks --- also violate real-time constraints leading to catastrophic loss of control. However, as this problem is known to be computationally hard, approximations are required particularly for larger graphs. We therefore propose a reconstruction algorithm for (directed) control graphs of bounded tree width embedded in Erdős-Rényi random graphs based on recent work by Aazami and Stilp as well as Guo et al.