2014/04/07 by Trefois, Maguy, Delvenne, Jean-Charles · 1 citation
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1405.6222
The zero forcing number is a graph invariant introduced to study the minimum rank of the graph. In 2008, Aazami proved the NP-hardness of computing the zero forcing number of a simple undirected graph. We complete this NP-hardness result by showing that the non-equivalent problem of computing the zero forcing number of a directed graph allowing loops is also NP-hard. The rest of the paper is devoted to the strong controllability of a networked system. This kind of controllability takes into account only the structure of the interconnection graph, but not the interconnection strengths along the edges. We provide a necessary and sufficient condition in terms of zero forcing sets for the strong controllability of a system whose underlying graph is a directed graph allowing loops. Moreover, we explain how our result differs from a recent related result discovered by Monshizadeh et al. Finally, we show how to solve the problem of finding efficiently a minimum-size input set for the strong controllability of a self-damped system with a tree-structure.