AF: Small: Algorithms meet Structural Graph Decomposition

图由点（称为顶点，代表对象）和这些点之间的线（称为边，代表边连接的对象之间的关系）组成。图和图算法在计算中起着至关重要的作用，并在所有科学中延伸。它们被用来对各种各样的对象进行建模，比如人和友谊（比如Facebook或LinkedIn等社交网络）、地图（谷歌地图）、大脑中神经元之间的连接，或者通过棋子的有效移动连接的棋盘上棋子的可能配置。由于这个原因，图被广泛研究，无论是从结构和计算的观点。图的结构方法通常试图解释当图具有某些期望的属性时，它必须“看起来像”什么。计算的观点寻求设计算法（高效的计算机程序），可以处理一个图来回答有关它的问题。例如，从一个地方（顶点）到另一个地方的最短路径是什么？哪个人在这个社交网络上是“最有影响力的？这个项目的目的是一个更紧密的联系之间的计算和结构的方法图。这样的连接已经存在-例如，许多图算法是基于强大的结构图分解。然而，结构分解在算法中的使用最常见的是黑盒方式-算法简单地利用定理提供的结构。由于结构定理的设计没有考虑到这些具体的算法应用，所得到的算法具有次优性能。对于其他重要的算法问题，现有的结构定理似乎“不太适合”，离开这些问题的有效算法只是遥不可及。在这个项目中，研究团队将证明新的算法关注的图结构定理，并使用新的结构定理来设计高效的算法。研究人员已经确定了几个方向，其中算法关注的结构定理有很大的成功潜力：图同构的minor-free图，加权图的优化问题，和（广义）切割和分离问题。在每个方向的研究团队将设计具有上级性能保证的全新算法，并采取远远超出最先进的领域。该项目切入理论计算机科学中几个著名的开放问题的核心，特别是在参数化算法和近似算法领域。如果输入图不包括一个以log log（n）顶点为次图的团，那么图同构是否存在多项式时间？删除尽可能少的顶点得到平面图的最佳近似算法是什么？平面图上未加权问题的近似方案能否提升到加权问题的近似方案？从一个有向图中去掉k个最小权的顶点使其成为非循环图的参数化复杂度是多少？这个项目是通过设计新的和算法有效的图分解定理来解决这些问题。新的分解定理将建立在全新的见解之上，以及结构图理论和算法的新颖组合。图论和算法思维的结合拥有大量尚未开发的潜力。因此，该项目的成果将在算法和结构图理论方面产生大量的新成果，并将使这两个领域更加紧密地联系在一起。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

A graph consists of dots, called vertices, representing objects, and lines between these dots, called edges, representing relationships between the objects the edge connects. Graphs and graph algorithms have a crucial role in computing, and by extension in all of science. They are used to model such diverse objects as people and friendships (social networks such as Facebook or LinkedIn), maps (Google Maps), connections between neurons in the brain, or the possible configurations of pieces on a chess-board connected by valid moves of chess pieces. For this reason graphs are extensively studied, both from structural and computational viewpoints. The structural approach to graphs often seeks to explain what a graph has to "look like" when it has certain desirable properties. The computational viewpoint seeks to design algorithms (efficient computer programs) that can process a graph to answer questions about it. For example, what is the shortest path from one place (vertex) to another? Which person on this social network is the "most influential?", etc. The aim of this project is a closer connection between the computational and the structural approaches to graphs. Such a connection already exists - for example many graph algorithms are based on powerful structural graph decompositions. However, the usage of structure decompositions in algorithms is most commonly in a black-box fashion - the algorithms simply exploit the structure provided by the theorems. Because the structure theorems were not designed with these concrete algorithmic applications in mind, the obtained algorithms have sub-optimal performance. For other important algorithmic problems the existing structure theorems seem to “not quite fit”, leaving efficient algorithms for these problems just out of reach. In this project the team of researchers will prove new algorithmically-focused graph-structure theorems, and use the new structure theorems to design efficient algorithms.The investigator has identified several directions where algorithmically-minded structure theorems have a big potential for success: graph isomorphism on minor-free graphs, optimization problems on weighted graphs, and (generalized) cut and separation problems. In each of these directions the team of researchers will design radically new algorithms with superior performance guarantees, and take the field far beyond the state of the art. The project cuts to the heart of several well-known open problems in theoretical computer science, specifically within the fields of parameterized algorithms and approximation algorithms. Is there a polynomial time for graph isomprohism if the input graphs exclude a clique with log log(n) vertices as a minor? What is the best approximation algorithm for deleting the fewest possible vertices to get a planar graph? Can approximation schemes for unweighted problems on planar graphs be lifted to their weighted counterparts? What is the parameterized complexity of removing k vertices of minimum weight from a digraph to make it acyclic? This project is to resolve these problems by designing new and algorithmically efficient graph-decomposition theorems. The new decomposition theorems will be built on completely new insights, as well novel combinations of insights from structural graph theory and algorithms. The combination of graph-theoretic and algorithmic thinking holds a wealth of untapped potential. Therefore the results of this project will yield substantial new results both in algorithms and in structural graph theory, and will bring the two fields closer together.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.