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 language | English (US) |
|---|---|
| Title of host publication | 2022 American Control Conference, ACC 2022 |
| Publisher | Institute of Electrical and Electronics Engineers Inc. |
| Pages | 1444-1449 |
| Number of pages | 6 |
| ISBN (Electronic) | 9781665451963 |
| DOIs | |
| State | Published - 2022 |
| Event | 2022 American Control Conference, ACC 2022 - Atlanta, United States Duration: Jun 8 2022 → Jun 10 2022 |
Publication series
| Name | 2022 American Control Conference (ACC) |
|---|
Conference
| Conference | 2022 American Control Conference, ACC 2022 |
|---|---|
| Country/Territory | United States |
| City | Atlanta |
| Period | 6/8/22 → 6/10/22 |
Bibliographical note
Publisher Copyright:© 2022 American Automatic Control Council.
Keywords
- Strong structural controllability
- dynamics over graphs
- zero forcing sets