On the edge insertion/deletion and controllability distance of linear structural systems

Yuan Zhang, Tong Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

13 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages2300-2305
Number of pages6
ISBN (Electronic)9781509028733
DOIs
Publication statusPublished - 28 Jun 2017
Externally publishedYes
Event56th IEEE Annual Conference on Decision and Control, CDC 2017 - Melbourne, Australia
Duration: 12 Dec 201715 Dec 2017

Publication series

Name2017 IEEE 56th Annual Conference on Decision and Control, CDC 2017
Volume2018-January

Conference

Conference56th IEEE Annual Conference on Decision and Control, CDC 2017
Country/TerritoryAustralia
CityMelbourne
Period12/12/1715/12/17

Fingerprint

Dive into the research topics of 'On the edge insertion/deletion and controllability distance of linear structural systems'. Together they form a unique fingerprint.

Cite this