Collaborative Research: Zero Forcing on Graphs: Computation and Applications

Iowa State University, Ames IA

Investigators

Abstract

The concept of networks is a mathematical term used to analyze relationships between objects (e.g. people, places, and things). Of particular importance is the study of how influence propagates throughout networks, especially how one can deduce the influence of an entire network by monitoring a few members. The objective of this project is to establish a comprehensive knowledge base for developing, implementing, and applying computational methods related to this phenomenon. As a result, this research has strong connections to applications related to social networks, electrical power networks, and quantum systems. This project also supports a concerted effort to engage underrepresented groups within the research. Hence, the impact of this educational component includes the development of underrepresented groups within the next generation of STEM researchers. The main technical contribution of this project is the integration of combinatorial optimization, spectral graph theory, and numerical analysis techniques to examine zero-forcing in networks. In particular, the research team will incorporate branch decomposition techniques and linear and integer programming techniques to significantly increase the computational efficacy of algorithms to solve zero-forcing problems on graphs. The models and algorithms that result from this study will be validated using experimental data and also by data attainable publicly like electrical grid data. This research will significantly advance the knowledge base of combinatorial optimization, integer programming, and spectral graph theory while also contributing to the increased scalability and efficiency for solving computationally hard problems related to the aforementioned applications.