Approximation of Controllability Graphs via Power Dominating Set

Controllability offers a comprehensive, rigorous and detailed framework for the design and analysis of not only control systems, but also of networks requiring a control relationship between vertices. The safe, secure, and effective operation of critical infrastructures such as electric power relies on the ability to monitor the state of a given system or network, or more formally the ability to observe the state and to estimate the state of a system. The problem of Structural Controllability offers a graph theoretical interpretation for control systems, which is particularly suitable for studying sets of nodes offering the ability to control an entire system as represented by a control graph. The identification of minimum Driver Nodes (DN ) via the Maximum Matching offers full control over the network and an obvious target for attackers to disrupt these relations or compromise intermediate nodes, thereby gaining partial or total control of a distributed system. This offers a strong motivation to study the ability of such systems to recover from deliberate attacks.

This thesis studies the alternative approach based on the POWER DOMINATING SET (PDS) problem, which gives an equivalent formulation for identifying minimum Driver Nodes. We therefore review existing work on graph classes, for which a PDS has been studied before, identifying a possible embedding of such structures in Erdös-Rényi graphs of different density as well as the approximation characteristics, which can be achieved in order to adapt them for solving the directed PDS problem. We therefore propose a reconstruction algorithm for (directed) control graphs of bounded tree-width embedded in Erdös-Rényi random graphs. This algorithm considers the rapid reconstruction of a PDS under attack as the more critical requirement relative to optimising the resulting PDS.

We also obtain an enhanced average-case complexity of the recovery algorithm based on a DFS structure after an event or attack leading to disrupt legitimate control and compromise controllability of dependent nodes or disconnect parts of the control original graph. Furthermore, we address the question of how to recover a control graph as far as possible if the PDS or its dependent nodes have been partially compromised without complete re-computation. Finally, we study the effect of rewiring edges on the Structural Controllability properties of directed Erdös-Rényi graphs in order to achieve a minimal PDS while keeping the total number of edges unchanged.