Leader Selection for Strong Structural Controllability in Networks using Zero Forcing Sets

Waseem Abbas, Mudassir Shabbir, Yasin Yazicioglu, Xenofon Koutsoukos

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

This paper studies the problem of computing a minimum zero forcing set (ZFS) in graphs. The problem is important because it is directly related to the leader selection problem for the strong structural controllability of networks defined over graphs. Computing a ZFS of minimum size is a well-known NP-hard problem in general. We show that previously known greedy heuristic could give arbitrarily bad solutions for some graphs. We study the problem on trees and present an optimal algorithm to compute a minimum ZFS in linear time in trees. For general graphs, we present a game-theoretic solution by formalizing the minimum ZFS problem as a potential game. Finally, we numerically evaluate our results on random graphs.

Original languageEnglish (US)
Title of host publication2022 American Control Conference, ACC 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages1444-1449
Number of pages6
ISBN (Electronic)9781665451963
DOIs
StatePublished - 2022
Event2022 American Control Conference, ACC 2022 - Atlanta, United States
Duration: Jun 8 2022Jun 10 2022

Publication series

Name2022 American Control Conference (ACC)

Conference

Conference2022 American Control Conference, ACC 2022
Country/TerritoryUnited States
CityAtlanta
Period6/8/226/10/22

Bibliographical note

Publisher Copyright:
© 2022 American Automatic Control Council.

Keywords

  • dynamics over graphs
  • Strong structural controllability
  • zero forcing sets

Fingerprint

Dive into the research topics of 'Leader Selection for Strong Structural Controllability in Networks using Zero Forcing Sets'. Together they form a unique fingerprint.

Cite this