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

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

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.