Dilation Choice Sets, Dulmage–Mendelsohn Decomposition, and Structural Controllability

One of the two conditions for the controllability of linear structured systems is a rank condition. It can be phrased as the absence of so-called dilations in the directed graph representing the system. Starting from dilations in the graph of a system without control, input vertices and edges can be added such that these dilations are removed. Their presence can be investigated by searching for minimal dilations, and by combining them into larger ones, leading to the recently introduced notion of dilation choice set. However, from a computational point of view, this searching for minimal dilations is not efficient as their number may grow rapidly. For this reason, in this article, first a fundamental decomposition of the related bipartite graph is recalled. The decomposition, called the Dumage–Mendelsohn decomposition, can be obtained by well-known and efficient methods. With the decomposition, the dilations can be found and removed in a straightforward way, making sure that the rank condition for structural controllability is fulfilled. Using a refined version of the decomposition, this process can even be refined. Finally, the relevance of vertices and edges for the removal of dilations can be characterized.