Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks

Massachusetts Institute Of Technology, Cambridge MA

Investigators

Abstract

Networks are everywhere, from gene regulatory networks, brain networks, and health/disease networks, to online social networks. This project will develop frameworks for algorithms to better understand, analyze, and manipulate such networks. The resulting algorithms will provide provable guarantees on both how much computation time they require and on the quality of the computed solution, enabling new analysis tools for real-world networks. The researchers will also co-develop a new graduate course about network algorithms and the underlying technologies of fixed-parameter algorithms, approximation algorithms, and algorithmic graph theory. The investigators plan to publish a textbook on the topics covered in this project to further their educational impact. Instead of developing individual algorithmic solutions to a specific problem (the typical approach in the field of algorithms), this project will develop very general algorithmic frameworks that apply to an entire category of problems all at once. In this way, the investigators approach a general theory of graph algorithms, wherein a given problem of interest can simply be adapted into the general approach. The project considers the two main types of algorithms for solving NP-hard graph optimization problems. Approximation algorithms allow the result to be a small factor away from the optimal, but still requires polynomial time. Parameterized algorithms allow the running time to be exponential, but only with respect to a parameter other than the problem size, while the result must be optimal. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.