On the structural output controllability and functional observability of undirected networks

In this paper, we investigate the structural output controllability (SOC) and structural functional observability (SFO) of undirected networks. We first characterize the generic dimensions of controllable subspace and output controllable subspace of undirected networks, relating them to either the generic ranks of simple products of matrices without the symmetric weight constraint, or maximum linkings of certain dynamic graphs. Our results show that, with or without the symmetric weight constraint, these dimensions always coincide. Our characterizations also induce a maximum flow based algorithm for computing the generic dimension of output controllable subspace in O(n^2.5) time (n is the system state dimension). This challenges a claim of its NP-hardness in a recent work. Additionally, we demonstrate that minimizing the number of driver nodes required to achieve SOC of undirected networks can be solved in O(n^2.5) time. We also show that this problem becomes NP-hard if the driver nodes need to be dedicated. Building on these results, we further develop criteria for the SFO of undirected networks, which are not directly dual to the SOC. Our approach is purely graph-theoretic, based on the dynamic graphs of undirected networks, not relying on the eigenspace of symmetric matrices. As a by-product, we also present alternative proofs for the criteria of structural (output) controllability of undirected networks.