Minimal Edge Addition for Network Controllability

We address the problem of optimally modifying the topology of a directed dynamical network to ensure structural controllability. More precisely, given the structure of a directed dynamical network (i.e., an existing networked infrastructure), we propose a framework to find the minimum number of directed edges that need to be added to the network topology in order to render a structurally controllable system. Our main contribution is twofold: first, we provide a full characterization of all optimal network modifications, and second, we propose an algorithm able to find an optimal solution in polynomial time. We illustrate the validity of our algorithm via numerical simulations in random networked systems.