New Frontiers in Parameterizing Away from Triviality

图是现实世界系统中常用的模型。图有两种元素：顶点和边。顶点表示系统的单个组件，而边表示这些组件之间的链接或关系。图模型在各个领域的普遍存在使得图算法的设计和分析成为计算机科学和离散数学的一个丰富的子领域。不幸的是，在实践中出现的许多相关图问题在理论上是np困难的（本质上意味着它们不太可能有有效的算法）。这促使人们寻找特殊的结构，使问题在具有这种结构的输入上易于解决。事实上，有大量的研究致力于识别特定的图族，在这些图族上可以有效地解决某些NP-hard图问题。因此，如果给定的模型恰好属于这些族（称为图类）中的任何一个，那么可以有效地解决各种问题。一些著名的图类是——完全图（每一对顶点都由一条边连接），有界度图（每个顶点都连接到少量其他顶点），低直径图（每个顶点都可以从任何顶点通过沿着几条边到达）。不幸的是，尽管在现实世界中观察到的网络具有一些似乎可利用的结构特征，但它们通常不能完全归入从理论模型中获得的严格定义的图类。但是，如果观察到的网络不包含在特定的图类中，但与该类中的图相似，除了一些不同之处，该怎么办？是否可以将在这个图类上工作的有效算法提升到那些不包含在类中，但仍然相当“接近”它的图的有效算法？例如，假设我们想要查询图中所有边上累积事件的最小顶点集。如果我们的图是完全图，那么这个查询可以被有效地回答。但是，如果我们的图“接近”完成，也就是说，除了几对顶点外，其他每对顶点都有一条边连接呢？同样的问题还能得到有效的回答吗？答案是肯定的！因此，在过去的十年中，已经有了一个系统的努力，将有效的算法从图类提升到接近类的图。这项工作的一个关键挑战是理解“接近”的含义。对图与图类的接近度进行数学建模的一种常用方法是通过各种图编辑距离的概念。这些只是在给定图中需要添加/删除的顶点和/或边的数量（称为编辑操作），以达到图类中的某些图。这些图形编辑距离的概念在高效算法的设计中发挥了重要作用，特别是在被称为参数化复杂性的算法的活跃子领域。该项目旨在通过正式引入新的和更复杂的图编辑距离概念，并研究它们对np困难问题的有效可解性的影响，在这一领域取得重大进展。这些编辑距离的概念不像传统的那样取决于编辑操作的数量，而是取决于它们的固有结构。参数化复杂性的成功表明，研究相关对象的结构，而不是只考虑它们的大小，可以对计算问题的有效可解性产生强大的影响。总之，该项目将为建立在图之间“结构编辑距离”上的高级算法理论奠定基础，为基本问题开发新的算法，并发现迄今为止未知的可有效解决的实例。该项目涉及算法中的一个基础研究课题，并将为理论计算机科学的这一子领域的重大进展做出贡献。

Graphs are a commonly used model of real-world systems. A graph has two types of elements: vertices and edges. The vertices represent individual components of a system and the edges represent links or relationships between these components. The ubiquity of graph models across various domains has led to the design and analysis of graph algorithms growing into a rich subarea of Computer Science and Discrete Mathematics. Unfortunately, many relevant graph problems that occur in practice are NP-hard in theory (essentially implying that they are unlikely to have efficient algorithms). This motivates the search for special structure that makes the problem easy to solve on those inputs possessing such structure. In fact, there is a vast amount of research devoted to identifying specific families of graphs on which certain NP-hard graph problems can be solved efficiently. Thus, if the given model happens to fall into any of these families (called graph classes), then one can solve various problems on it efficiently. Some well-known graph classes are -- complete graphs (each pair of vertices are linked by an edge), bounded-degree graphs (every vertex is linked to a small number of other vertices), low-diameter graphs (every vertex can be reached from any vertex by following few edges). Unfortunately, although networks observed in the real world have some structural characteristics that seem exploitable, they usually do not fall cleanly into rigidly defined graph classes obtained from theoretical models. But what if an observed network is not contained in a specific graph class, but resembles the graphs in this class, except for a few differences? Could one lift efficient algorithms that work on this graph class, to efficient algorithms for those graphs that are not contained within the classes, yet are still reasonably "close" to it? For example, suppose that we want to query for a smallest set of vertices that are cumulatively incident on all the edges in our graph. If our graph is a complete graph, then this query can be answered efficiently. But what if our graph is "close" to complete, that is, except for a few pairs of vertices, every other pair of vertices has an edge linking them? Could the same query still be answered efficiently? The answer turns out to be, yes! Thus, in the last decade, there has been a systematic effort to lift efficient algorithms from graph classes to graphs close to the classes. A key challenge in this effort is to understand what "close" means. A common way of mathematically modelling the proximity of a graph to a graph class is via various notions of graph edit distance. These are simply the number of vertices and/or edges one needs to add/remove (called edit operations) in the given graph, to reach some graph in the graph class. These notions of graph edit distance have been instrumental in the design of efficient algorithms, especially in the active subarea of algorithmics called Parameterized Complexity.This project aims to take a significant stride forward in this area by formally introducing new and more complex notions of graph edit distance and studying their impact on efficient solvability of NP-hard problems. These notions of edit distance will depend not on the number of edit operations as they traditionally have, but on their inherent structure. The success of parameterized complexity has shown that studying the structure of relevant objects as opposed to only considering their size, can have a powerful impact on efficient solvability of computational problems. In summary, this project will lay the foundations for an advanced algorithmic theory built on "structural edit distances" between graphs, develop new algorithms for fundamental problems and uncover hitherto unknown efficiently solvable instances. The project deals with a fundamental research topic in algorithmics and will contribute towards major advances in this subarea of theoretical computer science.