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

网络无处不在，从基因调控网络、大脑网络、健康/疾病网络，到在线社交网络。该项目将为算法开发框架，以更好地理解、分析和操纵此类网络。由此产生的算法将在它们需要多少计算时间和计算解决方案的质量上提供可证明的保证，从而为现实世界的网络启用新的分析工具。研究人员还将共同开发一门新的研究生课程，内容涉及网络算法以及固定参数算法、近似算法和算法图论的基础技术。研究人员计划就这个项目所涵盖的主题出版一本教科书，以进一步提高他们的教育效果。这个项目将开发非常通用的算法框架，同时适用于整个类别的问题，而不是为特定的问题开发单独的算法解决方案(算法领域的典型方法)。通过这种方式，研究人员接近了图形算法的一般理论，其中给定的感兴趣的问题可以简单地改编成一般方法。该项目考虑了解决NP-Hard图优化问题的两种主要类型的算法。近似算法允许结果偏离最优的一个小因素，但仍然需要多项式时间。参数化算法允许运行时间是指数级的，但只针对问题大小以外的参数，而结果必须是最优的。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

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.