On Leader Selection for Strong Structural Controllability in Matrix-Weighted Networks
arXiv:2607.28168
The paper addresses the NP‑hard problem of choosing a smallest set of leader nodes that ensure strong structural controllability in matrix‑weighted networks, presenting a two‑phase method with symmetry‑breaking algorithms and theoretical guarantees.
Abstract
The inverse synthesis problem of selecting a minimal leader set to guarantee strong structural controllability (SSC) in matrix-weighted networks remains an unresolved NP-hard challenge. This paper proposes a rigorous mathematical framework to solve this. We prove that structural uncontrollability stems exclusively from dimension-specific reachability isolation and topological symmetry equivalence. To overcome these bottlenecks, we formulate a two-phase synthesis: a reachability prerequisite to identify structural roots, followed by three distinct symmetry-breaking algorithms (Greedy Weisfeiler-Lehman Selection, Submodular Bound Maximization, and Partition Entropy Maximization). Mathematical proofs guarantee immunity to invariant subspaces and structural dilation, validated by extensive numerical evaluations across diverse topologies.
8 pages