Zero forcing number, constrained matchings and strong structural controllability. (English) Zbl 1325.05057
Summary: The zero forcing number is a graph invariant introduced to study the minimum rank of the graph. In [Hardness results and approximation algorithms for some problems on graphs. Waterloo: University of Waterloo (PhD Thesis) (2008), http://hdl.handle.net/10012/4147], A. 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 N. Monshizadeh, S. Zhang and M. K. Camlibel [“Zero forcing sets and controllability of dynamical systems defined on graphs”, IEEE Trans. Autom. Control 59, No. 9, 2562–2567 (2014, doi:10.1109/TAC.2014.2308619)]. 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.
MSC:
| 05C05 | Trees |
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 15A03 | Vector spaces, linear dependence, rank, lineability |
| 93B05 | Controllability |
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
References:
| [1] | Aazami, A., Hardness results and approximation algorithms for some problems on graphs (2008), University of Waterloo, PhD thesis |
| [2] | AIM minimum rank - special graphs work group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl., 428, 1628-1648 (2008) · Zbl 1135.05035 |
| [3] | Barioli, F.; Fallat, S.; Hershkowitz, D.; Hall, H. T.; Hogben, L.; van der Holst, H.; Shader, B., On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra, 18, 126-145 (2009) · Zbl 1169.05345 |
| [4] | Burgarth, D.; Bose, S.; Bruder, C.; Giovannetti, V., Local controllability of quantum networks, Phys. Rev. A, 79, 6, 060305(R) (2009) |
| [5] | Burgarth, D.; D’Alessandro, D.; Hogben, L.; Severini, S.; Young, M., Zero forcing, linear and quantum controllability for systems evolving on networks, IEEE Trans. Automat. Control, 58, 2349 (2013) · Zbl 1369.93079 |
| [6] | Burgarth, D.; Giovannetti, V., Full control by locally induced relaxation, Phys. Rev. Lett., 99, 10, 100501(R) (2007) |
| [7] | Burgarth, D.; Yuasa, K., Quantum system identification, Phys. Rev. Lett., 108, 080502 (2012) |
| [8] | Camlibel, M. K.; Zhang, S.; Cao, M., Comments on “Controllability analysis of multi-agent systems using relaxed equitable partitions”, Int. J. Syst. Control Commun., 4, 112, 72-75 (2012) |
| [9] | Chapman, A.; Mesbahi, M., Strong structural controllability of networked dynamics, (Proc. American Control Conference (2013)), 6141-6146 |
| [10] | Egerstedt, M.; Martini, S.; Cao, M.; Camlibel, M. K.; Bicchi, A., Interacting with networks: how does structure relate to controllability in single-leader, consensus network?, Control Syst. Mag., 32, 4, 66-73 (2012) · Zbl 1395.93115 |
| [11] | Fallat, S.; Hogben, L., The minimum rank of symmetric matrices described by a graph: a survey, Linear Algebra Appl., 426, 558-582 (2007) · Zbl 1122.05057 |
| [12] | Godsil, C. D.; Severini, S., Control by quantum dynamics on graphs, Phys. Rev. A, 81, 5, 052316 (2010), 1:5 |
| [13] | Golumbic, M. C.; Hirst, T.; Lewenstein, M., Uniquely restricted matchings, Algorithmica, 31, 2, 139-154 (2001) · Zbl 0980.68084 |
| [14] | Hershkowitz, D.; Schneider, H., Ranks of zero patterns and sign patterns, Linear Multilinear Algebra, 34, 3-19 (1993) · Zbl 0793.05027 |
| [15] | Hogben, L., Spectral graph theory and the inverse eigenvalue problem of a graph, Chamchuri J. Math., 1, 51-72 (2009) · Zbl 1268.05125 |
| [16] | Hogben, L., Minimum rank problems, Linear Algebra Appl., 432, 8, 1961-1974 (2010) · Zbl 1213.05036 |
| [17] | Karp, R. M., Reducibility among combinatorial problems, (Miller, R. E.; Thatcher, J. W., Complexity of Computer Computations (1972), Plenum Press: Plenum Press New York), 85-104 · Zbl 1467.68065 |
| [18] | Lin, C.-T., Structural controllability, IEEE Trans. Automat. Control, AC-19, 3, 201-208 (Aug. 1974) · Zbl 0282.93011 |
| [19] | Liu, Y.-Y.; Slotine, J.-J.; Barabasi, A.-L., Controllability of complex networks, Nature, 473, 7346, 167-173 (May 2011) |
| [20] | Martini, S.; Egerstedt, M.; Bicchi, A., Controllability analysis of multi-agent systems using relaxed equitable partitions, Int. J. Syst. Control Commun., 2, 11213, 100-121 (2010) |
| [21] | Mayeda, H.; Yamada, T., Strong structural controllability, SIAM J. Control Optim., 17, 1, 123-138 (1979) · Zbl 0409.93011 |
| [22] | Mishra, S., On the maximum uniquely restricted matching for bipartite graphs, Electron. Notes Discrete Math., 37, 345-350 (2011) · Zbl 1268.68135 |
| [23] | Monshizadeh, N.; Zhang, S.; Camlibel, M. K., Zero forcing sets and controllability of dynamical systems defined on graphs, IEEE Trans. Automat. Control, 59, 9, 2562-2567 (2014) · Zbl 1360.93102 |
| [24] | Nabi-Abdolyousefi, M.; Mesbahi, M., On the controllability properties of circulant networks, IEEE Trans. Automat. Control, 58, 12, 3179-3184 (2013) · Zbl 1369.93086 |
| [25] | Olesky, D. D.; Tsatsomeros, M.; van den Driessche, P., Qualitative controllability and uncontrollability by a single entry, Linear Algebra Appl., 187, 183-194 (1993) · Zbl 0780.93012 |
| [26] | Parlangeli, G.; Notarstefano, G., On the reachability and observability of path and cycle graphs, IEEE Trans. Automat. Control, 57, 3, 743-748 (2012) · Zbl 1369.93382 |
| [27] | Rahmani, A.; Ji, M.; Mesbahi, M.; Egerstedt, M., Controllability of multi-agent systems from a graph theoretic perspective, SIAM J. Control Optim., 48, 1, 162-186 (2009) · Zbl 1182.93025 |
| [28] | Tanner, H. G., On the controllability of nearest neighbor interconnections, (Proc. of the 43rd IEEE Conference on Decision and Control (2004)), 2467-2472 |
| [29] | Yazicioglu, A. Y.; Abbas, W.; Egerstedt, M., A tight lower bound on the controllability of networks with multiple leaders, (Proc. of the 51st IEEE Conference on Decision and Control (2012)), 1978-1983 |
| [30] | Zhang, S.; Camlibel, M. K.; Cao, M., Controllability of diffusively-coupled multi-agent systems with general and distance regular topologies, (Proc. of the 50th IEEE Conference on Decision and Control and 2011 European Control Conference (2011)), 759-764 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
