TY - GEN
T1 - On the edge insertion/deletion and controllability distance of linear structural systems
AU - Zhang, Yuan
AU - Zhou, Tong
N1 - Publisher Copyright:
© 2017 IEEE.
PY - 2017/6/28
Y1 - 2017/6/28
N2 - This paper studies two related topology design problems: given a collection of links, including links among state variables or from existing inputs to state variables, each link with a cost, how to construct a system with the minimal link cost under structural controllability constraint; and conversely, how to determine the minimal cost of a link subset whose deletion eliminates the existence of a structural controllable system from the remaining links. We prove that both of these two problems are NP-hard. As for approximation, there exists a 2-Approximation algorithm for the first problem, and any multiplicative factor approximation for the minimal cost 1-block problem for bipartite graphs is also the approximation factor for the second problem. We also study two subproblems of the above problems, where the link candidates compose of Cartesian product among state variables and between state variables and existing inputs, and each link has a 0 - 1 cost. From a graph-Theoretical perspective, these subproblems can also be addressed equivalently as determining the graph edit distance of a linear structurally uncontrollable (respectively, controllable) system to its 'nearest' structurally controllable (respectively, uncontrollable) system with the same state variables and inputs, which extends the concept 'controllability distance' for numerical systems to linear structural systems. We give a polynomial time algorithm for the first subproblem, while the latter subproblem remains NP-hard. The complexity status of some variants of the above subproblems are also studied, where the insertable links are restricted in state links, or the deletable links are restricted in input ones.
AB - This paper studies two related topology design problems: given a collection of links, including links among state variables or from existing inputs to state variables, each link with a cost, how to construct a system with the minimal link cost under structural controllability constraint; and conversely, how to determine the minimal cost of a link subset whose deletion eliminates the existence of a structural controllable system from the remaining links. We prove that both of these two problems are NP-hard. As for approximation, there exists a 2-Approximation algorithm for the first problem, and any multiplicative factor approximation for the minimal cost 1-block problem for bipartite graphs is also the approximation factor for the second problem. We also study two subproblems of the above problems, where the link candidates compose of Cartesian product among state variables and between state variables and existing inputs, and each link has a 0 - 1 cost. From a graph-Theoretical perspective, these subproblems can also be addressed equivalently as determining the graph edit distance of a linear structurally uncontrollable (respectively, controllable) system to its 'nearest' structurally controllable (respectively, uncontrollable) system with the same state variables and inputs, which extends the concept 'controllability distance' for numerical systems to linear structural systems. We give a polynomial time algorithm for the first subproblem, while the latter subproblem remains NP-hard. The complexity status of some variants of the above subproblems are also studied, where the insertable links are restricted in state links, or the deletable links are restricted in input ones.
UR - http://www.scopus.com/inward/record.url?scp=85046293941&partnerID=8YFLogxK
U2 - 10.1109/CDC.2017.8263985
DO - 10.1109/CDC.2017.8263985
M3 - Conference contribution
AN - SCOPUS:85046293941
T3 - 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
SP - 2300
EP - 2305
BT - 2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
PB - Institute of Electrical and Electronics Engineers Inc.
T2 - 56th IEEE Annual Conference on Decision and Control, CDC 2017
Y2 - 12 December 2017 through 15 December 2017
ER -