Structural Controllability Analysis via Embedding Power Dominating Set Approximation in Erdos-Renyi Graphs

The ability of an attacker to take over control of a distributed system or to deny the defender the same is a general problem, but of particular significance in cyber-physical systems where even temporary loss of view or loss of control can result in outright failure and severe cascading effects. Moreover, many such cyber-physical systems not only exhibit a safe fail-stop behaviour such that they can be brought to a halt in a safe state, but also have hard real-time requirements such as in the case of electrical power networks and their constituent elements. We study the POWER DOMINATING SET (PDS) problem originally by Haynes to study the structure of electric power networks and their efficient control, known to be equivalent to the maximum matching problem. However, PDS is generally known to be NP-complete with poor approximability with recent work focusing on studying properties of restricted graph classes. In this paper we describe the problems of controllability and structural controllability as represented by the PDS problem and investigate different attacks affecting control networks. We therefore review existing work on graph classes for which PDS has been studied before identifying possible embeddings of such structures in Erdos-Renyi graphs of different density as well as the approximation characteristics which can be achieved in order to adapt them for solving the partition elements of directed PDS problem. This allows the rapid identification of feasible alternative control structures where attackers have damaged or compromised the original control network, and to recover partial controllability if a control network has been partitioned.