  This paper addresses problems on the robust structural design of complex
networks. More precisely, we address the problem of deploying the minimum
number of dedicated sensors, i.e., those measuring a single state variable,
that ensure the network to be structurally observable under disruptive
scenarios. The disruptive scenarios considered are as follows: (i) the
malfunction/loss of one arbitrary sensor, and (ii) the failure of connection
(either unidirectional or bidirectional communication) between a pair of
agents. First, we show these problems to be NP-hard, which implies that
efficient algorithms to determine a solution are unlikely to exist. Secondly,
we propose an intuitive two step approach: (1) we achieve an arbitrary minimum
sensor placement ensuring structural observability; (2) we develop a sequential
process to find minimum number of additional sensors required for robust
observability. This step can be solved by recasting it as a weighted set
covering problem. Although this is known to be an NP-hard problem, feasible
approximations can be determined in polynomial-time that can be used to obtain
feasible approximations to the robust structural design problems with
optimality guarantees.
