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 -