New Frontiers in Parameterizing Away from Triviality

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

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.