  In this paper, we study the maximum edge augmentation problem in directed
Laplacian networks to improve their robustness while preserving lower bounds on
their strong structural controllability (SSC). Since adding edges could
adversely impact network controllability, the main objective is to maximally
densify a given network by selectively adding missing edges while ensuring that
SSC of the network does not deteriorate beyond certain levels specified by the
SSC bounds. We consider two widely used bounds: first is based on the notion of
zero forcing (ZF), and the second relies on the distances between nodes in a
graph. We provide an edge augmentation algorithm that adds the maximum number
of edges in a graph while preserving the ZF-based SSC bound, and also derive a
closed-form expression for the exact number of edges added to the graph. Then,
we examine the edge augmentation problem while preserving the distance-based
bound and present a randomized algorithm that guarantees an approximate
solution with high probability. Finally, we numerically evaluate and compare
these edge augmentation solutions.
