Source-linked AI summary
Zero forcing sets and controllability of dynamical systems defined on graphs
Nima Monshizadeh, Shuo Zhang, Kanat Camlibel
TL;DR
The paper asks which leader vertices ensure controllability for systems whose matrices carry a directed graph's structure. It analyzes this family through zero forcing sets and establishes a one-to-one correspondence; for directed trees, path covers also give a minimum leader count and leader choices.
Problem
The paper studies which vertices must receive external inputs to ensure controllability for systems with graph-structured matrices.
Source: §I · p. 1Method
It analyzes controllability across a directed graph's qualitative class using zero forcing sets, including sufficiently rich subclasses.
Source: §I · p. 1Results
Takeaways & Limitations
For directed trees, a minimal path cover yields the minimum leader count, with its initial vertices serving as a leader choice.
Source: §I · p. 2
Abstract
from arXiv · showhide
In this paper, controllability of systems defined on graphs is discussed. We consider the problem of controllability of the network for a family of matrices carrying the structure of an underlying directed graph. A one-to-one correspondence between the set of leaders rendering the network controllable and zero forcing sets is established. To illustrate the proposed results, special cases including path, cycle, and complete graphs are discussed. Moreover, as shown for graphs with a tree structure, the proposed results of the present paper together with the existing results on the zero forcing sets lead to a minimal leader selection scheme in particular cases.
I. INTRODUCTION
For directed graph-structured systems, the paper links leaders that ensure controllability across a matrix family to zero forcing sets. This link also yields leader-selection results, including a path-cover rule for directed trees.
I. INTRODUCTION
- The model uses X for graph-associated dynamics and U to encode the vertices receiving external inputs, called leaders.The state is x and the input is u.Source: §I · p. 1
- Earlier work addressed graph-based controllability through topology and leader selection; zero-forcing conditions had also been studied for undirected graphs with same-sign off-diagonal entries.The paper treats strong structural controllability of a graph-structured matrix family through zero forcing, rather than the constrained-matching approach in.Source: §I · p. 1
- For the whole qualitative class of a directed graph, leaders ensure controllability exactly when they form a zero forcing set, so the minimum leader count equals the zero forcing number.The paper also studies sufficiently rich subclasses, where the converse need not hold for an arbitrary subset.Source: §I · p. 1
- The paper also examines path, cycle, and complete graphs, and connects its results to minimum-leader findings for Laplacian matrices.The introduction presents these cases as illustrations of the proposed results.Source: §I · pp. 1–2
- For directed trees, a minimal path cover gives the minimum leader count, and its initial vertices can be chosen as leaders.Checking whether a leader set controls every matrix in the qualitative class reduces to checking whether it is a zero forcing set.Source: §I · p. 2
II. PROBLEM FORMULATION AND MOTIVATION
The paper studies controllability across the family of matrices specified by a directed graph, rather than for one particular matrix. It frames leader selection for this family and connects the problem to zero forcing.
II. PROBLEM FORMULATION AND MOTIVATION
- For a graph G, ℓmin(G) is the smallest number of leaders that makes every system in the qualitative class controllable.Source: §II · p. 2
- Earlier leader-selection results considered Laplacians of undirected graphs, including path, cycle, and complete graph cases.Prior work also treated adjacency matrices and weak structural controllability.Source: §II · p. 2
- The target is controllability for systems whose matrices belong to the graph-defined qualitative class, not just a particular matrix realization.The systems use a fixed leader set and graph-structured matrices; examples include adjacency and Laplacian matrices.Source: §II · pp. 2–3
- The paper extends the leader-selection question to graph-defined matrix families and relates its analysis to zero forcing rather than constrained matching.Source: §II · p. 2
III. ZERO FORCING SETS
Zero forcing starts with a set of black vertices and repeatedly applies a directed color-change rule. A set is a zero forcing set when this process colors every vertex black.
III. ZERO FORCING SETS
- A black vertex forces its sole white out-neighbor to become black.Source: §III · p. 3
- The derived set D(C) contains the vertices black after applying the rule until no further changes are possible.Source: §III · p. 3
- A set Z is a zero forcing set when its derived set is the entire vertex set; Z(G) is the minimum size of such a set.Source: §III · p. 3
- In the illustrated example, {1} colors only {1, 2, 3, 4}, whereas {1, 5} is a zero forcing set and Z(G)=2.Source: §III · p. 3, Figure 1 · p. 3, Figure 2 · p. 3
IV. ZERO FORCING SETS AND CONTROLLABILITY
The section establishes that controllability for a graph and leader set is equivalent to that set being a zero forcing set. It derives the minimum leader count and shows that controllability is preserved by the coloring process.
IV. ZERO FORCING SETS AND CONTROLLABILITY
- Adding a vertex forced by the current coloring preserves controllability, so controllability is equivalent for C and its derived set D(C).Source: §IV · pp. 3–4
- A leader set renders the graph-defined family controllable if and only if it is a zero forcing set.Source: §IV · p. 4
- The converse proof rules out a controllable leader set whose coloring process leaves vertices white, using a rank argument over the qualitative class.Source: §IV · p. 4
- A zero forcing set also ensures every nonleader is accessible by a directed path from at least one leader.Source: §IV · p. 4
- The minimum number of leaders for controllability across the qualitative class equals the graph's zero forcing number.Source: §IV · p. 4
A. Sufficiently rich qualitative subclasses
For a qualitative subclass, controllability alone implies the zero-forcing criterion only under a richness condition. This distinguishes subclasses that preserve the full graph-based test from those that do not.
A. Sufficiently rich qualitative subclasses
- A zero forcing set controls every subclass of the graph's qualitative class, but controlling an arbitrary nonempty subclass need not imply zero forcing.For a four-vertex path, the singleton leader set {2} controls the Laplacian but is not a zero forcing set.Source: A. Sufficiently rich qualitative… · p. 4
- A leader set is a zero forcing set exactly when it controls the full qualitative class and, for sufficiently rich subclasses, the corresponding subclass.The paper defines sufficient richness through preservation of a left-null-vector relation when passing from the full class to the subclass.Source: A. Sufficiently rich qualitative… · pp. 4–5
- The symmetric subclass Qs(G1) is sufficiently rich, so it retains the qualitative-class controllability criterion.Undirected graphs correspond to directed graphs with symmetric arc sets, making this subclass relevant to such graph structures.Source: A. Sufficiently rich qualitative… · pp. 4–5
- If a graph vertex has at least two out-neighbors, the same-sign subclass Qss(G1) is not sufficiently rich.Ordinary Laplacian and adjacency matrices are among the special cases in this subclass.Source: A. Sufficiently rich qualitative… · p. 5
B. Special cases
The zero-forcing results recover minimum leader counts for undirected paths, cycles, and complete graphs across their qualitative classes. The section also gives a counterexample to extending that agreement to all graphs and a path-cover characterization for directed trees.
B. Special cases
- For paths, cycles, and complete graphs, the minimum leader counts are respectively 1, 2, and n −1 for both Laplacians and all matrices in the corresponding qualitative classes.The undirected graph is represented by a directed graph with symmetric arcs; the zero forcing numbers match these counts.Source: B. Special cases · p. 5, Figure 3 · p. 6
- A 10-vertex 6-regular circulant has ℓmin(L) = 2, yet no pair of vertices is a zero forcing set.Thus the agreement in the path, cycle, and complete cases does not hold for every graph.Source: B. Special cases · pp. 5–6
- For a directed tree T, the minimum leader count equals its path cover number P(T).Initial points of the vertex-disjoint paths in a minimal path cover form a minimal zero forcing set.Source: B. Special cases · p. 6
V. CONCLUSION
The paper relates controllability across a directed graph's qualitative class to zero forcing sets. Existing zero-forcing results then yield minimal leader counts and selections in particular graph classes, including trees.
V. CONCLUSION
- For the qualitative class of a directed graph, the leader sets that ensure controllability for all its matrices correspond one-to-one with zero forcing sets.The paper also treats controllability for subclasses through the notion of sufficiently rich subclasses.Source: §V · p. 6
- Known zero-forcing results yield minimum leader counts and, in particular cases such as trees, minimal leader-selection schemes.For graph classes whose zero forcing number is known, the paper states that the corresponding minimum leader count and, in principle, a minimal selection scheme follow.Source: §V · p. 6