Source-linked AI summary
Zero forcing number, constrained matchings and strong structural controllability
Maguy Trefois, Jean-Charles Delvenne
TL;DR
The paper asks whether zero-forcing NP-hardness extends to loop-directed graphs and how strong controllability can be expressed using graph structure. It connects zero forcing with constrained matchings, establishes the loop-directed hardness result, and gives a polynomial-time minimum-input result for self-damped tree systems.
Problem
The paper addresses the complexity of zero forcing on loop-directed graphs and the challenge of finding minimum-size input sets for strong controllability.
Source: §4 · p. 10, §7 · p. 17Method
It uses a one-to-one correspondence between zero forcing sets and constrained matchings in the associated bipartite graph to formulate strong controllability through zero forcing.
Source: §1 · p. 5, §7 · p. 17Results
Computing loop-directed zero forcing is NP-hard, strong S-controllability is equivalent to S being a zero forcing set, and minimum-size inputs for self-damped tree systems can be found in polynomial time.
Source: §7 · pp. 17–18Takeaways & Limitations
For self-damped systems, minimum zero forcing sets in the simple interconnection graph provide minimum-size strong-controllability input sets, with polynomial-time selection for trees.
Source: §1 · p. 6, §7 · p. 18The paper expects NP-hardness for loop-undirected zero forcing but notes that a thorough argument is still needed.
Source: §7 · p. 18
Abstract
from arXiv · showhide
The zero forcing number is a graph invariant introduced to study the minimum rank of the graph. In 2008, Aazami proved the NP-hardness of computing the zero forcing number of a simple undirected graph. We complete this NP-hardness result by showing that the non-equivalent problem of computing the zero forcing number of a directed graph allowing loops is also NP-hard. The rest of the paper is devoted to the strong controllability of a networked system. This kind of controllability takes into account only the structure of the interconnection graph, but not the interconnection strengths along the edges. We provide a necessary and sufficient condition in terms of zero forcing sets for the strong controllability of a system whose underlying graph is a directed graph allowing loops. Moreover, we explain how our result differs from a recent related result discovered by Monshizadeh et al. Finally, we show how to solve the problem of finding efficiently a minimum-size input set for the strong controllability of a self-damped system with a tree-structure.
1 Introduction
The introduction frames zero forcing as a graph invariant connected to minimum rank, then develops its use in strong controllability. It also announces NP-hardness for loop-directed graphs and a polynomial-time result for self-damped systems on trees.
1 Introduction
- A zero forcing set is an initial vertex set whose repeated color changes eventually turn every vertex black; its minimum size is the zero forcing number.The rule differs by graph type: in a loop-directed graph, a vertex with exactly one white out-neighbor can change it, possibly itself.Source: §1 · pp. 2–3
- Computing the zero forcing number of a loop-directed graph is NP-hard, completing Aazami’s result for simple undirected graphs.The different color-change rules mean the simple-graph and loop-directed problems cannot be reduced to one another.Source: §1 · p. 4
- Structural controllability considers the interconnection graph’s structure rather than the strengths of its edges, which may be unknown or only partly determined.When edge weights are not known, the classical Kalman condition cannot be used.Source: §1 · p. 4
- Strong controllability from an input set is characterized by zero forcing, and minimum zero forcing sets yield minimum-size inputs for self-damped systems.For self-damped systems with a tree structure, a minimum-size input set can be found in polynomial time.Source: §1 · pp. 5–6
- The paper links zero forcing sets in loop-directed graphs to constrained matchings in their associated bipartite graphs.This equivalence underlies the paper’s strong-controllability results.Source: §1 · p. 5
2 NP-hardness
This section extends zero-forcing NP-hardness from simple undirected graphs to loop-directed graphs. The proof transfers hardness through constrained matchings and triangle number.
2 NP-hardness
- Different color-change rules prevent reducing the simple-graph zero forcing problem to the loop-directed problem, or vice versa.The section treats the loop-directed case as a distinct hardness result.Source: §2 · p. 6
- The size of a maximum constrained matching in the associated bipartite graph equals the pattern’s triangle number, whose computation is NP-hard.The argument uses the relation between constrained matchings and triangle number, then between triangle number and zero forcing.Source: §2 · p. 7
- Computing the zero forcing number of any loop-directed graph is NP-hard.This completes the NP-hardness result for simple undirected graphs proved by Aazami.Source: §2 · pp. 6–7
3 Strong controllability: problem formulation
This section formulates strong controllability for systems whose interconnection graph is loop-directed. It asks whether a chosen input set guarantees controllability for every realization and how to find a smallest such set.
3 Strong controllability: problem formulation
- A loop-directed graph specifies the zero-nonzero pattern of the system matrix, while an input set specifies which vertices are directly controlled.The system matrix and input matrix range over realizations of their respective patterns.Source: §3 · p. 8
- A system is strongly S-controllable when every system realization associated with input set S is controllable.Controllability means the system can be driven from any initial state to any final state in finite time.Source: §3 · p. 8
- The section asks whether a given input set ensures strong controllability and how to find a minimum-size input set efficiently.These are posed as the two questions guiding the paper’s later results.Source: §3 · pp. 8–9
- Prior work characterized strong controllability using constrained matchings in the bipartite graph associated with the interconnection graph.The paper presents those results before developing its zero-forcing formulation.Source: §3 · p. 9
4 Strong controllability and constrained matchings
The section characterizes strong controllability through constrained matchings and identifies the difficulty of finding minimum-size input sets. For self-damped systems, the matching criterion yields a minimum-size input set, while zero forcing offers an efficient route for tree-structured systems.
4 Strong controllability and constrained matchings
- Strong controllability is equivalent to constrained matchings in the bipartite graph associated with the underlying loop directed graph.The criterion requires constrained (n − m)-matchings in A(S|.) and in A×(S|.) that are Vloop-less.Source: §4 · pp. 9–10
- For a self-damped system, a minimum-size input set is exactly the unmatched vertex set of a maximum constrained self-less matching.The unmatched vertices are taken from the V side of the associated bipartite graph.Source: §4 · pp. 9–10
- Computing a maximum constrained self-less matching remains challenging, despite providing a way to obtain a minimum-size input set for self-damped systems.The matching characterization is not itself an efficient solution to the minimum-input problem.Source: §4 · p. 10
- Zero forcing sets yield a polynomial-time way to select a minimum-size input set for a self-damped system with a tree structure.The paper combines its zero-forcing characterization with existing algorithms for zero forcing.Source: §4 · p. 10
- The matching-based minimum-size conclusion does not extend to undamped systems: the matching may produce an input set that is not minimum.The sufficient condition was also stated for undamped systems in, but the appendix gives a counterexample to its minimum-size implication.Source: §4 · p. 10
5 Strong controllability and zero forcing sets
The section translates strong controllability criteria from constrained matchings into zero forcing conditions. For self-damped systems, minimum zero forcing sets in the corresponding simple directed graph give minimum-size input sets, with an efficient solution for tree structures.
5 Strong controllability and zero forcing sets
- A chronological zero-forcing list corresponds exactly to a constrained matching in the bipartite graph associated with the loop directed graph.The unmatched vertices on the V side are the zero forcing set.Source: §5 · pp. 11–12
- A system is strongly S-controllable exactly when S is a zero forcing set of G and of G× with a chronological force list avoiding self-forces at vertices in Vloop.The restriction on G× is that no force i →i occurs for i ∈Vloop.Source: §5 · pp. 11, 13
- For a self-damped system, S is a minimum-size input set exactly when it is a minimum zero forcing set in the simple directed graph obtained by removing the loops.The looped graph underlying a self-damped system has a loop at every vertex.Source: §5 · p. 14
5.8. One can compute in polynomial time a minimum-size input set for strong controllability of a self-damped system with a tree-structure.
- Minimum zero forcing sets in simple directed graphs are NP-hard to compute, but existing algorithms allow efficient minimum-input selection for self-damped systems with tree structure.The NP-hardness inference is based on Aazami; the tree-structure result uses algorithms such as Algorithm 2.3 in.Source: §5 · p. 14
6 Related results
The section compares strong-controllability criteria for loop-directed systems with a related result for simple-directed systems. For self-damped systems, strong controllability is equivalent across the two formulations.
6 Related results
- The section explains how its loop-directed results differ from the related strong-controllability result of Monshizadeh et al..Source: §6 · pp. 15, 17
- The simple-directed matrix pattern has a free diagonal, unlike the pattern associated with a loop-directed graph, so its system family can be larger.The loop-directed system family is a subset of the simple-directed family; strong controllability of the larger family implies it for the subset, but not conversely.Source: §6 · pp. 15, 17
- For simple-directed graphs, strong S-controllability holds exactly when S is a zero forcing set of that graph.Source: §6 · p. 16
- With S = {1}, the loop-directed system is strongly controllable, but the associated simple-directed system is not.S is a zero forcing set of the loop-directed graph but not of its simple-directed counterpart.Source: Figure 2 · p. 16, §6 · p. 17
- For self-damped systems, strong controllability of the loop-directed system is equivalent to strong controllability of its associated simple-directed system.The equivalence is stated for a loop-directed graph underlying a self-damped system.Source: §6 · p. 17
7 Conclusion
The paper establishes NP-hardness for the zero forcing number of loop-directed graphs and connects zero forcing with strong controllability through constrained matchings. It concludes that minimum input sets for self-damped tree-structured systems can be found in polynomial time using existing zero-forcing algorithms.
7 Conclusion
- Computing the zero forcing number of any loop-directed graph is NP-hard, extending the result for simple undirected graphs.Source: §7 · p. 17
- Zero forcing sets in loop-directed graphs correspond one-to-one with constrained matchings in their associated bipartite graphs.Source: §7 · p. 17
- Testing strong S-controllability is equivalent to checking whether S is a zero forcing set in the loop-directed graph.Source: §7 · p. 18
- For self-damped systems, minimum zero forcing sets in the simple interconnection graph provide minimum-size strong-controllability input sets.Source: §7 · p. 18
- Existing zero-forcing algorithms give a polynomial-time method for finding a minimum-size input set for a self-damped system with tree structure.Source: §7 · p. 18
- The authors expect NP-hardness for loop-undirected graphs but state that a thorough argument is still needed.Source: §7 · p. 18
Appendix A
A counterexample exposes an error in a prior claim that a maximum constrained self-less matching yields a minimum input set for an undamped system. The corrected result guarantees an input set, not necessarily a minimum one.
Appendix A
- The prior corollary predicts an input set of size 2, but the example is strongly controllable from S = {1}.In the undamped example, the restricted patterns A(S|.) and A×(S|.) both have constrained 2-matchings.Source: Appendix A · p. 22
- None of the three self-less 2-matchings in A× is constrained, so its maximum constrained self-less matching has size 1.Source: Appendix A · p. 22
- The error is treating the self-less condition as sufficient for minimum input size: the constrained matchings in the two restricted patterns can differ, and the A× matching need not be self-less.Source: Appendix A · p. 23
- The corrected corollary says unmatched vertices from a maximum constrained self-less matching of A× form an input set for strong controllability of an undamped system.It does not claim that this input set is minimum-size.Source: Appendix A · p. 23