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 in Erdöos-Rényi random graphs to reduce the averagecase
complexity through partial re-use of PDS based on the formulation
of our recent work presented as an extended abstract