Computation of the Distance-based Bound on Strong Structural Controllability in Networks

Mudassir Shabbir, Waseem Abbas, Yasin Yazicioglu, Xenofon Koutsoukos

Research output: Contribution to journalArticlepeer-review


In this paper, we study the problem of computing a tight lower bound on the dimension of the strong structurally controllable subspace (SSCS) in networks with Laplacian dynamics. The bound is based on a sequence of vectors containing the distances between leaders (nodes with external inputs) and followers (remaining nodes) in the underlying network graph. Such vectors are referred to as the distance-to-leaders vectors. {We give exact and approximate algorithms to compute the longest sequences of distance-to-leaders vectors, which directly provide distance-based bounds on the dimension of SSCS. The distance-based bound is known to outperform the other known bounds (for instance, based on zero-forcing sets), especially when the network is partially strong structurally controllable. Using these results, we discuss an application of the distance-based bound in solving the leader selection problem for strong structural controllability. Further, we characterize strong structural controllability in path and cycle graphs with a given set of leader nodes using sequences of distance-to-leaders vectors. Finally, we numerically evaluate our results on various graphs.

Original languageEnglish (US)
JournalIEEE Transactions on Automatic Control
StateAccepted/In press - 2022

Bibliographical note

Publisher Copyright:


  • Approximation algorithms
  • Computer science
  • Controllability
  • Dynamic programming
  • dynamic programming
  • graph algorithms
  • Greedy algorithms
  • Heuristic algorithms
  • Laplace equations
  • network topology
  • Strong structural controllability


Dive into the research topics of 'Computation of the Distance-based Bound on Strong Structural Controllability in Networks'. Together they form a unique fingerprint.

Cite this