Skip to Main Content

The Many Face(t)s of Zero Forcing

Illya V. Hicks
Boris Brimkov

Introduction

What does getting good movie recommendations from Netflix have in common with monitoring the electrical power grid, searching for a fugitive who is trying to evade capture, and controlling a quantum system? All these tasks, and several others, can be modeled as the same graph optimization problem called zero forcing, and can be approached with the same battery of computational techniques. As an analogy, the zero forcing process can be thought of as a sudoku puzzle where through the limited information given, the rest of the missing information in the grid can be inferred. In this article, we outline several different settings where the zero forcing problem arose independently, and then discuss some of the solution techniques and remaining challenges related to the problem.

Figure 1.

Top Left: A minimum zero forcing set of the graph is marked by filled vertices (which represent blue vertices). The color changes are illustrated in each step from left to right, top to bottom.

Graphic without alt text

Zero forcing

We will begin with a purely graph-theoretic definition of zero forcing. Let be a graph and be a set of vertices initially colored blue, all other vertices being colored white. The color change rule dictates that at each timestep, a blue vertex with a single white neighbor may change the color of (or force) that neighbor to blue. Note that when several color changes are possible in a given timestep, they can be performed in any order or all at once. The closure of is the set of blue vertices obtained after the color change rule is applied iteratively until no more color changes are possible. A zero forcing set is a set whose closure is all of and the zero forcing number of , denoted , is the minimum cardinality of a zero forcing set. See Figure 1 for an illustration.

Minimum rank

A recommender system is a system that provides recommendations to users that best suit their preferences. Such systems are used by online retailers to suggest related products, by streaming platforms to suggest new songs or movies, and by dating sites to suggest potential matches. One of the key techniques used by recommender systems is based on the following idea: The recommender system has available a partially known preference matrix whose entry represents the preference of user toward product ; see Table 1 for an example.

Table 1.

A preference matrix for a movie recommender system.

\rotatebox[origin=c]{90}{\textbf{\textit{\;\;Bridesmaids\;\;}}} \rotatebox[origin=c]{90}{\textbf{\textit{Inception}}} \rotatebox[origin=c]{90}{\textbf{\textit{Star Wars}}} \rotatebox[origin=c]{90}{\textbf{\textit{Jaws 2}}}
Alice 0.85 0.91
Bob 0 0.33 0.79
Caleb 0.84 0.95
Daisy 0.67 0.45 0

The system assumes that the users can be grouped into a relatively small number of categories where users within each category have similar preferences for a given product and that products have a relatively small number of attributes that determine whether or not they are preferred by a given user. Then, in order to make good suggestions to the users, the recommender system tries to guess the unknown entries in the matrix so that the resulting matrix has minimum rank. The rank of this completed matrix can roughly be thought to correspond to the number of attributes of products or categories of users.

Due to its importance and prevalence, this matrix completion problem has received considerable attention and funding (such as the million-dollar Netflix prize Kor09). Many different variants of the minimum rank matrix completion problem have been studied. One variant, which is particularly attractive because it allows a graph theoretic representation of the problem, requires that the preference matrix be symmetric and that the only available information about its entries be whether they are zero or nonzero. Thus, such a preference matrix can be thought of as a “matrix pattern” encompassing all possible completions that fit the pattern.

More formally, let be a set of ordered pairs such that , , and if then . A symmetric matrix pattern indexed by is the set of all real symmetric matrices whose entry is

We will say that a real symmetric matrix fits the pattern of if . Moreover, since is symmetric, we can also think of it as a weighted adjacency matrix of a graph; we will say that a graph corresponds to if the adjacency matrix of fits the pattern of . Below is an example of a symmetric matrix pattern, the graph corresponding to that pattern, and two matrices that fit that pattern. In the matrix pattern, 0 denotes zero entries, * denotes nonzero entries, and ? denotes entries that could be zero or nonzero.

We will note here that in the literature, symmetric matrix patterns are more commonly defined as , where is a graph of order , is the set of all real symmetric matrices, and is the graph with vertices and edges . That way, the set of matrices is described by a graph, not the other way around. However, in the context of preference matrices for recommender systems, the graph is only a technical tool rather than the primary object of interest. Thus, we will proceed with our version of the definition.

With that, we define the minimum rank of an symmetric matrix pattern as the minimum rank over all matrices that fit the pattern, denoted . Similarly, the maximum nullity of is defined as . By the rank-nullity theorem, .

Since by definition the minimum rank is computed over an uncountably infinite family of matrices, direct computation of this parameter is very difficult. There are direct computation approaches (for example by finding Gröbner bases of several systems of polynomials Bri19), but they are prohibitively slow. Thus, research has instead focused on approximating or bounding the minimum rank of a matrix pattern by combinatorial or algebraic means. It was this goal of finding an accessible bound to the minimum rank that first gave rise to zero forcing AMRSGWG08.

We will illustrate this idea by computing the minimum rank of the matrix pattern shown above. Let

be a matrix which fits the pattern of and realizes , i.e., . Note that are nonzero real numbers, and are arbitrary real numbers. Let be a null vector of . Then, we have the following equations:

Suppose ; then, in 1, is forced to be zero; in 2, is forced to be zero (since and are zero), and in 3, is forced to be zero (since and are zero). Thus, if and , it follows that . Now, let and . Clearly, ; moreover, since we found that every nonzero in has , it follows that . By the well-known formula for the dimension of the intersection and sum of finite-dimensional subspaces, . Thus,

where the last inequality follows from the fact that . On the other hand, the matrix

fits the pattern of and has nullity 1, so . Thus, and hence .

What allows us to form an upper bound on in the example above is the choice of an appropriate set of indices , such that when for all , all other entries of are also forced to be zero. In particular, the principle by which a set of zero entries of forces other entries to be zero is precisely the color change rule in the graph corresponding to : when all-but-one terms in the left-hand-side of are zero for some row of , the remaining term (and the corresponding entry of ) must also be zero. For example, this is the case in 1 when choosing to be zero forces to be zero, which in turn forces and to be zero. Equivalently, selecting to be zero corresponds to choosing the end-vertex of the path as a zero forcing set of . This process is the source of the nomenclature of “zero forcing”! The same principles can be applied to any symmetric matrix pattern and the corresponding graph to obtain upper and lower bounds on (and hence on ); this is stated formally below.

Theorem 1 (AMRSGWG08).

Let be a symmetric matrix pattern, be the graph corresponding to , and be any matrix that fits the pattern of . Then, .

Thus, the zero forcing number can be used as a combinatorial bound on the minimum rank of a symmetric matrix pattern. Similar procedures have been developed for other types of matrix patterns (e.g., ones that are positive-semidefinite EEH13 or skew-symmetric IIrgomr10) using other types of graphs and color change rules; non-symmetric versions of zero forcing such as signed zero forcing have also been considered GB14. While both the graph-based parameters and the matrix-based parameters are difficult to compute, the former are generally much more tractable than the latter. Roughly speaking, in the worst case, evaluating a graph-based parameter such as for a graph with vertices requires operations while evaluating a matrix-based parameter such as for an matrix pattern requires operations. Thus, working with the graph-based parameters gives a significant computational advantage.

Power domination

Electric power networks consist of energy-producing generators, energy-consuming loads, transmission lines connecting the generators and loads, and busses where transmission lines intersect. An electric power company must constantly monitor the state of its network in order to detect system failures and assure that demands are being met. To this end, phase measurement units (PMUs) are placed at select locations around the network; these devices measure the voltage at the bus where they are placed, and the phase angle at the transmission lines incident with the bus. The PMU readings are then synchronized in processing stations, where the data from multiple PMUs is leveraged with physical laws governing the behavior of electrical circuits such as Ohm’s and Kirchoff’s laws in order to gain information about parts of the network which are not being directly monitored. Thus, the state of the entire network can be determined from partial information measured at appropriate locations. Because of the high cost of the equipment, labor, and communication infrastructure associated with installing and maintaining PMUs, electric power companies aim to use the smallest number of PMUs necessary to maintain full control of the network.

Electrical power networks can naturally be represented as graphs, where the generators, loads, and busses are vertices, and the transmission lines are edges. The problem of interest is then to select a minimum set of vertices, corresponding to the locations of PMUs, from which the entire graph can be observed. The rules by which vertices and edges can be observed are listed below (introduced in HHHH02); these rules reflect information gained by direct measurements of PMUs, as well as information gained through Ohm’s and Kirchoff’s laws about locations in the network which are not directly monitored by PMUs.

1.

All vertices at which a PMU is placed are observed.

2.

All edges incident to a vertex at which a PMU is placed are observed.

3.

A vertex incident to an observed edge is observed.

4.

An edge joining two observed vertices is observed.

5.

If a vertex is incident to edges and of these edges are observed, then all are observed.

This process is identical to zero forcing (where observed vertices are colored blue), with the exception that in the first timestep, by rules 2 and 3, every neighbor of an observed vertex is also observed. In other words, the set of vertices initially colored blue performs a “domination” step, and then the color change rule is applied iteratively as in zero forcing. Due to this domination step and the application to power network monitoring, this problem is referred to as power domination. A power dominating set is a set of vertices which causes the entire graph to be observed under the rules above, and the power domination number of a graph , denoted , is the minimum cardinality of a power dominating set of . Note that in a power dominating set, eventually all edges are observed, and in a non-power dominating set, the set of observed edges is the edge set of the graph induced by the observed vertices. Therefore, it is sufficient to only work with the observed vertices. See Figure 2 for an illustration.

Since a set is contained in its closed neighborhood, it follows that any zero forcing set is also a power dominating set. Thus, for any graph , . Moreover, is a power dominating set of if and only if is a zero forcing set, where is together with all neighbors of . Thus, if is a minimum power dominating set of and is the maximum degree of ,

Figure 2.

In the first panel, a minimum power dominating set is marked by shaded vertices. The second panel illustrates the domination step, and the remaining panels illustrate the other color changes.

Graphic without alt text

Due to these relations, zero forcing has been used as a technical tool in the derivation of various results about power domination.

Graph searching

Zero forcing also arose independently in the context of graph search problems. The objective of graph search problems is to capture a fugitive hidden on the vertices or edges of a graph while using a limited number of guards, search actions, or other resources. The earliest graph search problems that have received considerable attention are the edge search and node search problems, introduced by Megiddo et al. MHG88 and Kirousis and Papadimitriou KP86, respectively. In these problems, the aim is to capture an invisible fugitive using the smallest number of guards, where search actions consist of placing a guard at a vertex, removing a guard from a vertex, or sliding a guard along an edge. Bienstock and Seymour BS91 introduced the mixed search problem which combines the edge and node search problems, and focuses on minimizing the number of guards used at any step. Dyer et al. Dye08 introduced the fast search problem, which focuses on minimizing the number of search actions in which the fugitive is captured.

Yang Yan13 introduced the fast-mixed search problem, which combines the fast search and the mixed search models. In the fast-mixed search problem, an invisible fugitive can freely move at great speed from one vertex to another along a guard-free path. A vertex or edge where the fugitive may hide is contaminated, otherwise, it is cleared; a vertex is occupied if it has a guard on it. The search actions include placing a guard on a contaminated vertex and sliding a guard along a contaminated edge from to if is contaminated and all edges incident to except are cleared. A contaminated edge becomes cleared if both endpoints are occupied by guards or if a guard slides along it from one endpoint to the other. The fast-mixed search number of a graph , denoted is the minimum number of guards required to clear all edges of and therefore capture a fugitive hiding in . See Figure 3 for an illustration.

Figure 3.

Guards and clearing a graph. Cleared edges are indicated in bold. Note that the movement of the guards is identical to zero forcing color changes initiated by two blue vertices placed at the guards’ initial positions.

Graphic without alt text

Unexpectedly, it was later realized that the movements of the guards in the fast-mixed search model precisely coincide with the color changes in the zero forcing process initiated by blue vertices at the guards’ initial positions. Hence, fast-mixed searching and zero forcing are essentially the same problem, which yields the following identity.

Theorem 2 (FMY16).

For any graph , .

This relation allowed results and techniques developed for graph search algorithms to be applied to zero forcing and minimum rank problems, and vice versa BFH19.

Quantum control

Finally, zero forcing was also studied in quantum control theory under the name propagation, where it was introduced as a scheme for controlling large quantum systems by acting on small subsystems satisfying certain conditions. More precisely, a network of coupled spin quantum particles with Hamiltonian can be represented as a graph whose vertices are the spins of and whose edges are the non-Ising components of . The protocol for operating on this system through local quantum transformations can be described in graph terminology as follows: each vertex in an initially selected set has a packet of information that has to be diffused among all the vertices of the graph; a vertex can pass its packet to an adjacent vertex only if is the only neighbor of which still does not have the information Sev08. It is easy to see that this propagation protocol is identical to the zero forcing color change rule and that the smallest number of particles sufficient to control the system is the zero forcing number of the corresponding graph. This equivalence has enabled the use of techniques and results from zero forcing in quantum control theory, paving the way for applications like control of quantum hard drives and quantum RAM Bur07.

Learning the Ways of the Force

The zero forcing problem is difficult to solve directly, as it belongs to the class of NP-Hard optimization problems for which there are no efficient algorithms. Zero forcing appears to be difficult even when compared to other NP-Hard problems, since all the leading computational methods in the literature can only solve it for relatively small instances. Nevertheless, in light of its many applications, solving the zero forcing problem for moderately sized instances is an important practical task.

An obvious way to find a minimum zero forcing set of a graph is by brute force: simply consider all sets of vertices of size for and check whether the closure of each set is the whole graph. As soon as such a set is found, it is guaranteed to be a minimum zero forcing set since sets are checked in order of increasing size. However, since a graph on vertices could have zero forcing number as high as (e.g., if the graph is complete), this approach could require as many as sets to be checked.

The force is strong with this one

An improvement on the brute force method is the wavefront algorithm. This algorithm stores candidate vertex sets together with their closures, starting from singleton sets. Then, for each candidate set of a given size, the algorithm adds to one vertex that is outside the closure of and recomputes the closure. This is repeated until the closure of some candidate set is the entire graph; this candidate set must then be a minimum zero forcing set. The advantage of the wavefront algorithm BGH15BFH19 (whose name comes from the idea that closures are checked in “waves” according to the cardinalities of the underlying sets), is that it avoids checking a set of vertices if some subset of the set has the same closure. Thus, the algorithm tends to perform well in graphs where a small subset of vertices can force many other vertices. A downside of the wavefront algorithm is that it requires the simultaneous storage of a large number of closures. Thus, while the wavefront algorithm is often faster than other methods, it sometimes causes the computer to run out of memory.

Use the forts, Luke

A third approach to finding minimum zero forcing sets is to model the problem as an integer linear program (ILP) or a Boolean satisfiability (SAT) problem and use powerful ILP and SAT solvers to find a solution. An advantage of the ILP- and SAT-based algorithms is that they are more flexible and can accommodate additional constraints to the zero forcing problem. For example, they can ensure that the zero forcing set is connected or that the zero forcing set minimizes the number of forcing steps, which are problems of independent interest. Another advantage of ILP- and SAT-based algorithms is that they often give good upper and lower bounds on the zero forcing number even if they are stopped before they have time to find the exact solution.

Several different ways to model the zero forcing problem using ILP and SAT have been explored. One of the more robust models is based on the concept of forts. A fort of is a nonempty set such that every vertex that is outside and adjacent to has at least two neighbors in . See Figure 4 for an example. The name “fort” comes from the design of bastion forts, which made it possible for any nearby invader to be visible from at least two walls of the fort.

Figure 4.

Two of the forts of a graph indicated as gray areas. No vertex outside the fort has exactly one neighbor in the fort.

Graphic without alt text

Forts are an important concept in zero forcing because they indicate barriers that the forcing process must overcome. In particular, if all vertices outside a fort are colored blue and all vertices inside it are white, no vertex can penetrate the fort and force a vertex inside to turn blue. Therefore, in order for a set to be zero forcing, it must contain at least one vertex from every fort of the graph (a saboteur who opens the gates and lets the invaders in). The converse is also true.

Theorem 3 (CFaIVH18).

is a zero forcing set of if and only if intersects every fort of .

This theorem suggests the following simple ILP model to find a minimum zero forcing set (here if vertex is in the set and if vertex is not in the set):

A downside of this model is that a graph can have exponentially many forts. Thus, the fort constraints could require exponential time and space even simply to be written down. One way to overcome this problem is that instead of solving the ILP with all the fort constraints, we can instead solve a sequence of simpler ILPs each of which has only a small subset of the fort constraints. If chosen appropriately, one of these small subsets of constraints will subsume all the omitted constraints, and will yield an optimal solution. To illustrate this idea, let be the following graph:

In the first iteration, we will solve the ILP model without any fort constraints. The optimal solution to is clearly , which means our candidate set is empty. Since this set is not zero forcing, we find one single fort of that is not intersected by this set, for example, . In the next iteration, we will solve the ILP with just that fort constraint: . An optimal solution to that ILP is , which means our new candidate set is . Since this set is also not zero forcing, we find a single fort of that is not intersected by this set, for example, . In the next iteration, we add the fort constraint to the ILP. An optimal solution to this new ILP is , which means our new candidate set is . Since this set is in fact a zero forcing set, it satisfies every fort constraint of the ILP and minimizes the objective function. It is therefore a minimum zero forcing set and we terminate the algorithm. Thus, instead of having to find all the forts of , we only found two forts which subsumed all the others.

There are several ways of finding individual forts which are not intersected by a given candidate set. One way is to simply take the complement of the closure of the candidate set. Another way is to use a secondary ILP. The first way is the fastest, but may yield “low quality” forts that require a large number of iterations of the main ILP. The second way can be calibrated to find either the “highest quality” forts at a high computational cost, or “medium quality” forts at a medium computational cost. Finding a fort generation subroutine which results in the best trade-off between the number of iterations and the cost per iteration is an active area of research.

While the solution methods discussed above can compute the zero forcing numbers of graphs with several hundred vertices, other optimization problems such as the maximum clique problem, the minimum vertex cover problem, and the traveling salesman problem can be solved for graphs with thousands and sometimes hundreds of thousands of vertices. One simple reason is that these problems have been around for many decades longer than zero forcing, and have been attacked by many more researchers who have continuously improved the available solution approaches. A more nuanced and technical reason could be explained by the polyhedral structure of the zero forcing problem. The constraints in the model above (and indeed in any ILP model) can be viewed as hyperplanes in . The intersection of those hyperplanes is a convex set in called a polyhedron. The “sides” of this surface are called facets; see Figure 5 for an illustration. Knowing the facets of a polyhedron helps ILP solvers find an optimal solution. On the other hand, if a polyhedron has a large number of facets, it can be inherently difficult to solve problems on that polyhedron with integer programming and other methods. In BMH21 it was shown how the facets of the zero forcing polyhedron corresponding to certain commonly occurring forts in the graphs can be characterized. It was also shown that the number of these facets can be exponential (around for a graph of order ). This suggests that the zero forcing problem may be inherently difficult, at least in graphs whose forts have those structures.

Figure 5.

A polyhedron in with one facet shown in white with a bold border.

Graphic without alt text

Forts are interesting not just from a computational point of view but also from an algebraic point of view. For example, the following result shows that the forts of a graph have a connection to the kernel of its adjacency matrix:

Theorem 4 (HBD22).

Let be a graph of order and let . There exists a matrix that fits the same matrix pattern as the adjacency matrix of such that if and only if the indices of the nonzero entries of form a fort of .

In addition, forts can characterize the circuits of matroids linked to the minimum rank of a matrix pattern HBD22. Hence, forts are very interesting structures and should be explored further.

Conclusion

Zero forcing is a multifaceted problem with connections to many areas of mathematics and many practical applications. The wide interest in zero forcing has created a rapidly growing and diverse research community that has generated a large volume of work in the last few years. There are many remaining computational and theoretical challenges to resolve, as well as deeper connections to linear algebra and matroid theory that may be just the tip of an iceberg. The zero forcing community is excited to welcome a new generation of mathematicians to this problem and see what new discoveries and advancements we can forge together.

Acknowledgments

We thank two anonymous referees for their valuable remarks and suggestions which greatly improved the article.

References

[Kor09]
Yehuda Koren, The Bellkor solution to the Netflix grand prize, Netflix prize documentation 81 (2009), 1–10.,
Show rawAMSref \bib{koren2009}{article}{ author={Koren, Yehuda}, journal={Netflix prize documentation}, pages={1--10}, title={The {B}ellkor solution to the {N}etflix grand prize}, volume={81}, year={2009}, }
[Bri19]
Boris and Scherr Brimkov Zachary, An exact algorithm for the minimum rank of a graph, Preprint, arXiv:1912.00158, 2019.,
Show rawAMSref \bib{brimkov5}{eprint}{ author={Brimkov, Boris and Scherr, Zachary}, arxiv={1912.00158}, title={An exact algorithm for the minimum rank of a graph}, year={2019}, }
[AMRSGWG08]
AIM Minimum Rank-Special Graphs Work Group, Zero forcing sets and the minimum rank of graphs, Linear Algebra Appl. 428 (2008), no. 7, 1628–1648, DOI 10.1016/j.laa.2007.10.009. MR2388646,
Show rawAMSref \bib{AIM-Workshop}{article}{ author={AIM Minimum Rank-Special Graphs Work Group}, title={Zero forcing sets and the minimum rank of graphs}, journal={Linear Algebra Appl.}, volume={428}, date={2008}, number={7}, pages={1628--1648}, issn={0024-3795}, review={\MR {2388646}}, doi={10.1016/j.laa.2007.10.009}, }
[EEH13]
Jason Ekstrand, Craig Erickson, H. Tracy Hall, Diana Hay, Leslie Hogben, Ryan Johnson, Nicole Kingsley, Steven Osborne, Travis Peters, Jolie Roat, Arianne Ross, Darren D. Row, Nathan Warnberg, and Michael Young, Positive semidefinite zero forcing, Linear Algebra Appl. 439 (2013), no. 7, 1862–1874, DOI 10.1016/j.laa.2013.05.020. MR3090441,
Show rawAMSref \bib{positive_zf2}{article}{ author={Ekstrand, Jason}, author={Erickson, Craig}, author={Hall, H. Tracy}, author={Hay, Diana}, author={Hogben, Leslie}, author={Johnson, Ryan}, author={Kingsley, Nicole}, author={Osborne, Steven}, author={Peters, Travis}, author={Roat, Jolie}, author={Ross, Arianne}, author={Row, Darren D.}, author={Warnberg, Nathan}, author={Young, Michael}, title={Positive semidefinite zero forcing}, journal={Linear Algebra Appl.}, volume={439}, date={2013}, number={7}, pages={1862--1874}, issn={0024-3795}, review={\MR {3090441}}, doi={10.1016/j.laa.2013.05.020}, }
[IIrgomr10]
IMA-ISU research group on minimum rank, Minimum rank of skew-symmetric matrices described by a graph, Linear Algebra Appl. 432 (2010), no. 10, 2457–2472, DOI 10.1016/j.laa.2009.10.001. IMA-ISU research group members: Mary Allison, Elizabeth Bodine, Luz Maria DeAlba, Joyati Debnath, Laura DeLoss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader and Amy Wangsness Wehe. MR2608168,
Show rawAMSref \bib{skew_forcing}{article}{ author={IMA-ISU research group on minimum rank}, title={Minimum rank of skew-symmetric matrices described by a graph}, note={IMA-ISU research group members: Mary Allison, Elizabeth Bodine, Luz Maria DeAlba, Joyati Debnath, Laura DeLoss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader and Amy Wangsness Wehe }, journal={Linear Algebra Appl.}, volume={432}, date={2010}, number={10}, pages={2457--2472}, issn={0024-3795}, review={\MR {2608168}}, doi={10.1016/j.laa.2009.10.001}, }
[GB14]
Felix Goldberg and Abraham Berman, Zero forcing for sign patterns, Linear Algebra Appl. 447 (2014), 56–67, DOI 10.1016/j.laa.2013.11.049. MR3200206,
Show rawAMSref \bib{signed_zf}{article}{ author={Goldberg, Felix}, author={Berman, Abraham}, title={Zero forcing for sign patterns}, journal={Linear Algebra Appl.}, volume={447}, date={2014}, pages={56--67}, issn={0024-3795}, review={\MR {3200206}}, doi={10.1016/j.laa.2013.11.049}, }
[HHHH02]
Teresa W. Haynes, Sandra M. Hedetniemi, Stephen T. Hedetniemi, and Michael A. Henning, Domination in graphs applied to electric power networks, SIAM J. Discrete Math. 15 (2002), no. 4, 519–529, DOI 10.1137/S0895480100375831. MR1935835,
Show rawAMSref \bib{powerdom3}{article}{ author={Haynes, Teresa W.}, author={Hedetniemi, Sandra M.}, author={Hedetniemi, Stephen T.}, author={Henning, Michael A.}, title={Domination in graphs applied to electric power networks}, journal={SIAM J. Discrete Math.}, volume={15}, date={2002}, number={4}, pages={519--529}, issn={0895-4801}, review={\MR {1935835}}, doi={10.1137/S0895480100375831}, }
[MHG88]
N. Megiddo, S. L. Hakimi, M. R. Garey, D. S. Johnson, and C. H. Papadimitriou, The complexity of searching a graph, J. Assoc. Comput. Mach. 35 (1988), no. 1, 18–44, DOI 10.1145/42267.42268. MR926173,
Show rawAMSref \bib{fms1}{article}{ author={Megiddo, N.}, author={Hakimi, S. L.}, author={Garey, M. R.}, author={Johnson, D. S.}, author={Papadimitriou, C. H.}, title={The complexity of searching a graph}, journal={J. Assoc. Comput. Mach.}, volume={35}, date={1988}, number={1}, pages={18--44}, issn={0004-5411}, review={\MR {926173}}, doi={10.1145/42267.42268}, }
[KP86]
Lefteris M. Kirousis and Christos H. Papadimitriou, Searching and pebbling, Theoret. Comput. Sci. 47 (1986), no. 2, 205–218, DOI 10.1016/0304-3975(86)90146-5. MR881212,
Show rawAMSref \bib{fms2}{article}{ author={Kirousis, Lefteris M.}, author={Papadimitriou, Christos H.}, title={Searching and pebbling}, journal={Theoret. Comput. Sci.}, volume={47}, date={1986}, number={2}, pages={205--218}, issn={0304-3975}, review={\MR {881212}}, doi={10.1016/0304-3975(86)90146-5}, }
[BS91]
D. Bienstock and Paul Seymour, Monotonicity in graph searching, J. Algorithms 12 (1991), no. 2, 239–245, DOI 10.1016/0196-6774(91)90003-H. MR1105476,
Show rawAMSref \bib{fms3}{article}{ author={Bienstock, D.}, author={Seymour, Paul}, title={Monotonicity in graph searching}, journal={J. Algorithms}, volume={12}, date={1991}, number={2}, pages={239--245}, issn={0196-6774}, review={\MR {1105476}}, doi={10.1016/0196-6774(91)90003-H}, }
[Dye08]
Danny and Yang Dyer Boting and Yaşar, On the fast searching problem, International Conference on Algorithmic Applications in Management, 2008, pp. 143–154.,
Show rawAMSref \bib{fms4}{inproceedings}{ author={Dyer, Danny and Yang, Boting and Ya{\c {s}}ar, {\"O}znur}, booktitle={International Conference on Algorithmic Applications in Management}, organization={Springer}, pages={143--154}, title={On the fast searching problem}, year={2008}, }
Boting Yang, Fast-mixed searching and related problems on graphs, Theoret. Comput. Sci. 507 (2013), 100–113, DOI 10.1016/j.tcs.2013.04.015. MR3110517,
Show rawAMSref \bib{fast_mixed_search}{article}{ author={Yang, Boting}, title={Fast-mixed searching and related problems on graphs}, journal={Theoret. Comput. Sci.}, volume={507}, date={2013}, pages={100--113}, issn={0304-3975}, review={\MR {3110517}}, doi={10.1016/j.tcs.2013.04.015}, }
[FMY16]
Shaun Fallat, Karen Meagher, and Boting Yang, On the complexity of the positive semidefinite zero forcing number, Linear Algebra Appl. 491 (2016), 101–122, DOI 10.1016/j.laa.2015.03.011. MR3440126,
Show rawAMSref \bib{zf_and_fms}{article}{ author={Fallat, Shaun}, author={Meagher, Karen}, author={Yang, Boting}, title={On the complexity of the positive semidefinite zero forcing number}, journal={Linear Algebra Appl.}, volume={491}, date={2016}, pages={101--122}, issn={0024-3795}, review={\MR {3440126}}, doi={10.1016/j.laa.2015.03.011}, }
[BFH19]
Boris Brimkov, Caleb C. Fast, and Illya V. Hicks, Computational approaches for zero forcing and related problems, European J. Oper. Res. 273 (2019), no. 3, 889–903, DOI 10.1016/j.ejor.2018.09.030. MR3907155,
Show rawAMSref \bib{brimkov_fast}{article}{ author={Brimkov, Boris}, author={Fast, Caleb C.}, author={Hicks, Illya V.}, title={Computational approaches for zero forcing and related problems}, journal={European J. Oper. Res.}, volume={273}, date={2019}, number={3}, pages={889--903}, issn={0377-2217}, review={\MR {3907155}}, doi={10.1016/j.ejor.2018.09.030}, }
[Sev08]
Simone Severini, Nondiscriminatory propagation on trees, J. Phys. A 41 (2008), no. 48, 482002, 10, DOI 10.1088/1751-8113/41/48/482002. MR2515873,
Show rawAMSref \bib{quantum2}{article}{ author={Severini, Simone}, title={Nondiscriminatory propagation on trees}, journal={J. Phys. A}, volume={41}, date={2008}, number={48}, pages={482002, 10}, issn={1751-8113}, review={\MR {2515873}}, doi={10.1088/1751-8113/41/48/482002}, }
[Bur07]
Daniel and Giovannetti Burgarth Vittorio, Full control by locally induced relaxation, Physical Review Letters 99 (2007), no. 10, 100501.,
Show rawAMSref \bib{quantum1}{article}{ author={Burgarth, Daniel and Giovannetti, Vittorio}, journal={Physical Review Letters}, number={10}, pages={100501}, publisher={APS}, title={Full control by locally induced relaxation}, volume={99}, year={2007}, }
[CFaIVH18]
C. Fast and I. V. Hicks, The Effect of Vertex Degrees on the Zero-forcing Number and Iteration Index of a Graph, Discrete Applied Mathematics 250 (2018), 215-226.,
Show rawAMSref \bib{fast}{article}{ author={C. Fast and I. V. Hicks}, journal={Discrete Applied Mathematics}, pages={215-226}, title={The Effect of Vertex Degrees on the Zero-forcing Number and Iteration Index of a Graph}, volume={250}, year={2018}, }
[BGH15]
Steve Butler, Jason Grout, and H. Tracy Hall, Using variants of zero forcing to bound the inertia set of a graph, Electron. J. Linear Algebra 30 (2015), 1–18, DOI 10.13001/1081-3810.2900. MR3318426,
Show rawAMSref \bib{butler}{article}{ author={Butler, Steve}, author={Grout, Jason}, author={Hall, H. Tracy}, title={Using variants of zero forcing to bound the inertia set of a graph}, journal={Electron. J. Linear Algebra}, volume={30}, date={2015}, pages={1--18}, review={\MR {3318426}}, doi={10.13001/1081-3810.2900}, }
[BMH21]
Boris Brimkov, Derek Mikesell, and Illya V. Hicks, Improved computational approaches and heuristics for zero forcing, INFORMS J. Comput. 33 (2021), no. 4, 1384–1399, DOI 10.1287/ijoc.2020.1032. MR4345594,
Show rawAMSref \bib{bmh}{article}{ author={Brimkov, Boris}, author={Mikesell, Derek}, author={Hicks, Illya V.}, title={Improved computational approaches and heuristics for zero forcing}, journal={INFORMS J. Comput.}, volume={33}, date={2021}, number={4}, pages={1384--1399}, issn={1091-9856}, review={\MR {4345594}}, doi={10.1287/ijoc.2020.1032}, }
[HBD22]
Illya V. Hicks, Boris Brimkov, Louis Deaett, Ruth Haas, Derek Mikesell, David Roberson, and Logan Smith, Computational and theoretical challenges for computing the minimum rank of a graph, INFORMS J. Comput. 34 (2022), no. 6, 2868–2872, DOI 10.1287/ijoc.2022.1219. MR4528889,
Show rawAMSref \bib{challenge}{article}{ author={Hicks, Illya V.}, author={Brimkov, Boris}, author={Deaett, Louis}, author={Haas, Ruth}, author={Mikesell, Derek}, author={Roberson, David}, author={Smith, Logan}, title={Computational and theoretical challenges for computing the minimum rank of a graph}, journal={INFORMS J. Comput.}, volume={34}, date={2022}, number={6}, pages={2868--2872}, issn={1091-9856}, review={\MR {4528889}}, doi={10.1287/ijoc.2022.1219}, }

Credits

Figures 1–5 are courtesy of Illya V. Hicks and Boris Brimkov.

Photo of Illya V. Hicks is courtesy of Carlyn Foshee.

Photo of Boris Brimkov is courtesy of Boris Brimkov.