Merging rules for strong structural controllability and minimum input problem in undirected networks

Abstract

This paper explores the conditions for strong structural controllability in structured networks determined by the zero/non-zero patterns of edges. For undirected networks, starting with the fundamental unit for controllability, the path graph, we investigate the strong structural controllability of larger components such as cycles, trees, and ultimately, a pactus (a generalization of the well-known cactus graph) through the merging rules. In this process, we introduce the notion of a component input node, which functions identically to an external input node, providing a new perspective on how internal nodes can facilitate controllability. Furthermore, we offer an intuitive interpretation by decomposing complex graph structures into simpler path graphs and applying merging rules to understand how disjoint controllable components can merge to maintain overall controllability. Finally, we present an algorithm to solve the minimum input problem in a pactus, which leverages the concept of component input nodes to optimize the number of external inputs for strong structural controllability. © 2025 The Franklin Institute