Minimal controllability problem on linear structural descriptor systems with forbidden nodes

Controllability analysis for large-scale network systems, such as multi-agent systems[1, 2], brain networks[3, 4], and power networks[5, 6] has received a great deal of interest in recent years, because it can be used to find important nodes [7]. Controllability analysis problems include:

• •

  quantitative problems; the maximization problems of controllability metrics [8, 9, 10, 11, 12].

• •

  qualitative problems; selecting input problems that render the system controllable [7, 13, 14, 15, 16].

The quantitative problems require the system parameters, which are not precisely determined in practical systems. In addition, quantitative problems often become computationally intractable when the state dimension becomes large. Conversely, the structural information of a system, i.e., the nonzero patterns of system parameters, is usually known. This is an advantage for qualitative problems that deal only with nonzero patterns. Also, it is known that the structural controllability [17] of a structural system can be checked efficiently using graph algorithms. Thus, for large-scale network systems, it is more appropriate to consider qualitative problems.

Therefore, we consider a Minimal Controllability Problem (MCP) of the following structural descriptor network system with state $x(t)\in\mathbb{R}^{n}$ and input $u(t)\in\mathbb{R}^{m}$, where $\mathbb{R}$ is the set of real numbers:

where $F,A\in\mathbb{R}^{n\times n},B\in\mathbb{R}^{n\times m}$, and $F\in\mathbb{R}^{n\times n}$ can be a singular matrix. That is, we assume that although the specific elements of $F$, $A$, and $B$ remain unknown, their nonzero patterns are known. The descriptor formulation aptly models practical systems featuring algebraic constraints, such as those found in electric circuit systems [18, 19, 20]. MCPs can be divided into two main problems[21]:

• •

  MCP0: A problem that finds an $n\times m$ matrix $B$ for system (1) to be structurally controllable where $m$ is minimum. For $F=I_{n}$ or $F\neq I_{n}$, efficient algorithms exist for solving MCP0 [7, 13, 14, 16].

• •

  MCP1: A problem that finds an $n\times n$ diagonal matrix $B$ for system (1) to be structurally controllable and the number of nonzero elements in $B$ is minimum [14]. Although a polynomial time algorithm exists [15] for a special case of (1) with $F\neq I_{n}$, MCP1 is known to be NP-hard [16] in general.

It should be noted that as mentioned in Section 3.2 in [22], there are only a few papers on MCP0 or MCP1 for system (1) with $F\neq I_{n}$ although just structural controllability analysis under the assumption of a given $(F,A,B)$ has been studied in [23, 19, 24].

The previous work in [16] on structural descriptor system (1) has not considered constraints on the input destination. There is a gap between practical situations since most physical systems have state variables to which inputs cannot be directly connected. For instance, consider a system in which the position $x(t)$ and velocity $v(t)$ of an object are the state variables. In this case, the state equation involves $\dot{x}(t)=v(t)$, but it does not make practical sense to add an input to this equation. Thus, specifying forbidden targets that cannot be connected to inputs is an important practical constraint. Therefore, [13] introduced forbidden nodes to MCP1 for system (1) with $F=I_{n}$. However, no work applies MCPs with $F\neq I_{n}$.

In this paper, we address MCP0 with forbidden nodes for structural descriptor system (1), because, in general, MCP1 for system (1) with $F\neq I_{n}$ is NP-hard, as shown in [16]. Here, the forbidden nodes correspond to the indices of “equations”, while those in [13], which studied (1) with $F=I_{n}$, correspond to the indices of “variables”. This naturally generalizes to $F\neq I_{n}$. In fact,

• •

  for $F=I_{n}$, the time evolution of $x_{i}$ is characterized by the $i$-th equation of (1). Thus, in this case, we can regard the index of equations as that of variables.

• •

  for $F\neq I_{n}$, the time evolution of $x_{i}$ is not characterized by the $i$-th equation of (1). Thus, in contrast to the case of $F=I_{n}$, here we cannot regard the index of equations as that of variables.

The contributions of this study can be summarized as follows.

• •

  We show a necessary and sufficient condition for the existence of the optimal solution of MCP0 with forbidden equations for structural descriptor system (1), which is described in the language of graph theory. This result is also useful in constructing the optimal solution.

• •

  We provide the optimal value of MCP0 with forbidden equations for structural descriptor system (1), by employing the graph-theoretic properties of the system, such as a bipartite graph and its Dulmage–Mendelsohn (DM) decomposition. The optimal value shows that the minimum number of input nodes is determined by a variant of the maximum matching problem with constraints on the matched nodes. This result includes that of the MCP0 without forbidden equations for descriptor system (1) [16].

• •

  We also provide an efficient algorithm for solving the above special matching problem by using the alternating path algorithm. The time complexity of this algorithm is $O(|V|+|E|\sqrt{|V|})$, which is on par with the algorithm for the MCP0 [7, 16] without forbidden equations, where $|V|$ and $|E|$ are the numbers of nodes and edges of the bipartite graph corresponding to descriptor system (1), respectively.

The remainder of this paper is organized as follows. The basic concepts of graph theory are summarized in Section II. The formulation of MCP0 with forbidden equations for structural descriptor systems is described in Section III. In Section IV, we provide the analysis and the algorithm of MCP0 with forbidden equations for the descriptor system (1). The conclusions are presented in Section V.

In this section, we present a comprehensive overview of the fundamental concepts of graph theory that are used in this paper.

A strongly connected component (SCC) of a directed graph with node set $V$ is a maximal subset $C\subseteq V$ whose nodes $u,v\in C$ can be connected by a directed path on the graph.

Let $G=(V^{+},V^{-};E)$ be a bipartite graph. For an edge $e=(v^{+},v^{-})\in E$, $\partial^{+}e$ and $\partial^{-}e$ denote the nodes of $v^{+}\in V^{+}$ and $v-\in V^{-}$, respectively. That is, $\partial^{+}:E\rightarrow V^{+}$ and $\partial^{-}:E\rightarrow V^{-}$. The edge set $M\subseteq E$ is a matching if it does not share nodes of each edge. A matching $M$ is termed maximum matching if $M$ contains the largest possible number of edges. We define symbol $\nu(G)$ as the size of a maximum matching of $G$.

We introduce the DM decomposition for a bipartite graph $G=(V^{+},V^{-};E)$, which is the unique decomposition algorithm for bipartite graphs (see [19] for details). Algorithm 1 describes DM decomposition. We define $M$ as a maximum matching of $G$ and an auxiliary directed graph $\tilde{G}_{M}$. The edges of $\tilde{G}_{M}$ are oriented from $V^{+}$ to $V^{-}$ except for $M$. The decomposition is illustrated in Fig. 1.

Subgraphs $G_{k}\ (k=0,\dots,b,\infty)$ in Step 6 of Algorithm 1 are called DM components of $G$. $G_{k}\ (k=1,\dots,b)$ are called consistent DM components; $G_{0}$ and $G_{\infty}$ are called inconsistent DM components. The order $G_{i}\preceq G_{j}$ for the consistent DM components $G_{i}$ and $G_{j}$ is defined as

“There is a directed path on $\tilde{G}_{M}$ from $G_{j}$ to $G_{i}$,”

and the order between the consistent DM component $G_{i}$ and inconsistent DM components $G_{0}$ and $G_{\infty}$ are defined as $G_{0}\preceq G_{i}$ and $G_{i}\preceq G_{\infty}$, respectively. Then, $\preceq$ is a partial order. Moreover, the decomposition constructed by Algorithm 1 does not depend on an initially chosen maximum matching $M$ of $G$ in step 1), as shown in Lemma 2.3.35 in [19]. For example, in Fig. 1, there is a directed edge from $G_{2}$ to $G_{1}$, and thus

The greatest computational bottleneck in the construction of the DM decomposition is to find the maximum matching of $G$. This can be achieved in $O(|E|\sqrt{|V|})$ by using the augmentation path algorithm [25]. Thus, the computational complexity of DM decomposition is $O(|E|\sqrt{|V|})$.

In this section, we formulate MCP0 with forbidden equations for the descriptor system (1).

First, we assume that system (1) is solvable, i.e., for any initial state $x(0)$ with an admissible input $u(t)$, there exists a unique solution $x(t)$ to Eq. (1). This condition is equivalent to

where $s$ is an indeterminant [19] [26].

In this paper, we call system (1) controllable if for any admissible initial state $x(0)$ that satisfies equation (1), there exists an input $u(t)$ and a final time $T\geq 0$ such that $x(T)=0$. This controllability is usually referred to as R-controllability. Additional controllability concepts can be found within the framework of descriptor system theory [27].

An algebraic characterization of controllability can be described as follows [26, 27]:

System (1) is termed structurally controllable if condition (3) in Proposition 1 holds for (1) with generic matrices $F$, $A$, and $B$. It should be noted that a matrix is considered generic if each nonzero element is an independent parameter. For a more precise definition of the generic matrix, see [19].

For instance, consider descriptor system (1) with

Then, $R=\{e_{1},e_{2},\dots,e_{5}\}$. Let $\mathcal{F}=\{e_{3},e_{4}\}$ be the set of indices of forbidden equations. The matrices

satisfy condition II).

In this section, we provide the analysis and the algorithm of MCP0 with forbidden equations for descriptor system (1) with generic matrices using a graph-theoretic approach.

To this end, we first describe the graph representation of the descriptor system (1) with generic matrices and graph-theoretical controllability. Although there are several graph representations for descriptor system (1) [24, 28, 19], we used the bipartite graph representation [19] in this study. While the directed graph representation is common for system (1) with $F=I_{n}$, the bipartite graph representation is often used for $F\neq I_{n}$ [23].

The bipartite graph $G=(V^{+},V^{-};E)$ associated with descriptor system (1) is defined as follows: the node sets $V^{+}$ and $V^{-}$ are defined as

where the state node set $X$ and the input node set $U$ are defined as

respectively, and $e_{i}$ in $V^{-}$ corresponds to the $i$-th equation of system (1). That is, $V^{+}$ consists of state variables and inputs, and $V^{-}$ is the set of indices of equations. Then, the edge set $E$ is defined as

with $E_{A}:=\{(e_{i},x_{j})\mid A_{ij}\neq 0\}$, $E_{F}:=\{(e_{i},x_{j})\mid F_{ij}\neq 0\}$ and $E_{B}=\{(e_{i},u_{j})\mid B_{ij}\neq 0\}$. An edge belonging to $E_{F}$ is termed an s-arc. We also define important subgraphs of $G$ as $G_{A-sF}=(X,V^{-};E_{A}\cup E_{F})$, $G_{\left[A\mid B\right]}=(V^{+},V^{-};E_{A}\cup E_{B})$, and $G_{A}=(X,V^{-};E_{A})$. For example, the bipartite representation of descriptor system (1) with (6) and $B_{2}$ in (7), and its subgraphs are illustrated in Fig. 2.

Furthermore, for a DM component of $\mathcal{G}$ that has s-arcs [16], we call it a DM s-component, where $\mathcal{G}$ is $G$ or $G_{A-sF}$. Let $G_{k}\ (k=0,\dots,b,\infty)$ be DM components of $\mathcal{G}$, and $G_{k}\ (k=1,\dots,b)$ are called consistent DM components; $G_{0}$ and $G_{\infty}$ are termed inconsistent DM components. The maximal consistent DM s-component is a consistent DM s-component $G_{k}$ of $\mathcal{G}$ such that no other DM s-components are greater than $G_{k}$ related to the partial order $\preceq$. Note that there can be multiple maximal consistent DM s-components.

For instance, consider descriptor system (1) with parameters given in (6). The corresponding DM decomposition of the bipartite representation $G_{A-sF}$ is depicted in Fig. 3. $G_{1}$, $G_{2}$, and $G_{3}$ are the consistent DM components of $G_{A-sF}$, and $G_{3}\preceq G_{2}\preceq G_{1}$. That is, a maximal consistent DM s-component of this graph is $G_{1}$, because there is no edge to enter $G_{1}$ from other DM components.

The following graph-theoretic characterization of structural controllability for descriptor system (1) is found in [19].

Condition 1) represents the solvability of the system described in Eq. (2) in Section III, and the latter two conditions correspond to (3) in Proposition 1. From assumption (2), condition 1) in Proposition 2 is always satisfied. Assumption (2) also implies that there are no inconsistent DM components $G_{0}$ and $G_{\infty}$ of $G_{A-sF}$. This is because if we choose a maximum matching $M$ with a size of $n$ in $G_{A-sF}$, then $V_{0}$ and $V_{\infty}$ in Steps 3–4 in Algorithm 1 are both empty.

The following lemma describes the characterization of the consistent DM components of $G_{A-sF}$ and $G$.

For instance, consider descriptor system (1) with (6) and $B_{1}$ in (7). The DM decomposition of the bipartite representation $G$ is depicted in Fig. 4. $G_{0}$ is the inconsistent DM component, $G_{1}$ is the consistent DM component, and $G_{0}\preceq G_{1}$. That is, $G_{1}$ is the maximal consistent DM s-component. Then, the consistent DM component $G_{1}$ in $G_{A-sF}$ (Fig 3) is also consistent in $G$ (Fig. 4), since there is no directed path from $u_{1}$ to $e_{2}$ or $x_{1}$ in $G$. Note that in general, there is a directed path from $u\in U$ to $x\in X$, because edges in a matching are undirected.

Lemma 1 gives another characterization of the structural controllability condition for system (1) which satisfies solvability condition (2). This property will be used in the proof of Theorem 1 in the next subsection.

Consider descriptor system (1) with $A$ and $F$ given in (6) and $B_{1}$ in (7) again. In $G_{A-sF}$, there is no directed path from $u_{1}$ to $G_{1}$ (Fig. 4). This means condition 3’) in Corollary 1 does not hold. Thus, descriptor system (1) with (6) and $B_{1}$ in (7) is not structurally controllable.

In this study, we introduced the forbidden equations to MCP0 for structural descriptor systems. We gave a necessary and sufficient condition for the existence of solutions to the problem and provided the solution to MCP0. The algorithm for solving the problem can be computed in polynomial time as for the standard MCP0. That is, our proposed algorithm is well positioned for applications to large-scale descriptor systems.

In this paper, we focused on MCP0 for a structural descriptor system, since, for a structural descriptor system, MCP1 is NP-hard in general as shown in [16]. Thus, finding a solvable condition for MCP1 with forbidden equations in polynomial time would be a future project.

Furthermore, structural controllability considered in this paper requires that the system parameters be algebraically independent. This means that all non-zero system parameters are free, which may be a strong assumption for practical situations. To avoid this assumption, strong structural controllability has been proposed in [29], and studied from a graph-theoretic perspective in [30]. A strong structural controllability problem version in this paper is one of the future works.

This work was supported by the Japan Society for the Promotion of Science KAKENHI under Grant 20K14760 and 23K03899.