Structure of Hereditary Graph Classes and Its Algorithmic Consequences

开发有效的算法来解决组合问题是非常重要的现代技术社会。许多问题出现在不同的领域，如运输，电信，分子生物学，工业工程等，当通过图建模时，简化为诸如找到最大团（其是全部成对相邻的节点的集合）、或稳定集合（其是没有一个节点是成对相邻的节点的集合）、或着色问题（即，使用最小数量的颜色来对图的顶点着色，使得没有两个相邻顶点接收相同的颜色）的大小的问题。不幸的是，这些基本的优化问题，以及许多其他重要的广泛的应用程序，是NP-难解决的一般。这意味着，计算机不太可能有一种有效的方法来解决这些问题（即不太可能存在多项式时间算法来解决这些问题）。当限制到特殊类时，它们变成多项式时间可解的，但即使在输入图上强加了似乎相当多的结构时，它们也仍然是困难的。Robertson和Seymour在他们著名的Graph Minors Project中阐明了在顶点删除和边的删除和收缩（minor-closed）下封闭的图类的结构。它们的结构特征对算法产生了深远的影响。在应用程序中出现的图类不一定是小闭的，它们更一般地只是遗传的。关于它们的结构可以说些什么？不太可能期望如此强大的结构性结果与广泛的算法后果，就像小封闭类的情况一样。此外，正如对几个复杂遗传图类的研究所证明的那样，在研究小闭类中开发的一套工具不足以更普遍地研究遗传类。也许最著名的遗传类，已经研究了过去50年，是完美图类。该课程由Berge于1961年引入，他的动机是研究传播理论。这门课激发了来自不同领域的大量研究。Berge著名的强完美图猜想是用分解定理证明的。该分解定理使用的割集与小闭类分解中使用的割集有根本不同。我们还知道，完美图可以在多项式时间内识别。该领域的关键问题是，对于完美图，是否有可能通过纯图论的多项式时间算法来解决相关的优化问题（团，稳定集，染色和团覆盖顶点）。(It已知它可以使用椭圆体方法间接完成）。像这样的问题激发了拟议中的研究。解决这些问题需要开发新的工具和技术来更普遍地研究遗传类。在过去的几十年里，通过使用分解获得了许多重要的结果，其中人们通过将复杂的结构分解为更简单的部分来理解它。一些非常有趣的遗传类现在在结构上得到了很好的理解，但是对于其中的一些（特别是那些需要类似于用于分解完美图的割集的割集），仍然不清楚如何在算法上利用它们的结构。该项目将专注于几个适当选择的遗传图类的结构和计算研究，目的是更普遍地洞察遗传类的结构，并洞察计算可行性的边界。

Developing efficient algorithms for solving combinatorial problems is of great importance to the modern technological society. Many problems arising in diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc., when modeled by graphs reduce to problems such as finding the size of a largest clique (which is a set of nodes that are all pairwise adjacent), or stable set (which is a set of nodes none of which are pairwise adjacent), or the coloring problem (i.e. using the minimum number of colors to color the vertices of a graph so that no two adjacent vertices receive the same color). Unfortunately these fundamental optimization problems, and many others essential for wide spectrum of applications, are NP-hard to solve in general. This means that it is highly unlikely that there will ever be an efficient way to solve them by a computer (i.e. it is unlikely that polynomial time algorithms exist for these problems). They become polynomial time solvable when restricted to special classes, but also remain difficult even when seemingly quite a lot of structure is imposed on an input graph. Understanding structural reasons that enable efficient algorithms for combinatorial problems on hereditary graph classes (i.e. those closed under vertex deletion) is the primary interest of this proposal.Robertson and Seymour, in their famous Graph Minors Project, elucidated the structure of graph classes that are closed under vertex deletion, and deletion and contraction of edges (i.e. minor-closed). Their structural characterization had far-reaching algorithmic consequences. The graph classes that appear in applications are not necessarily minor-closed, they are more generally just hereditary. What can be said about their structure? It is unlikely to expect such strong structural results with sweeping algorithmic consequences, as was the case with minor-closed classes. Furthermore, as was already evidenced by the study of several complex hereditary graph classes, the set of tools developed in the study of minor-closed classes does not suffice to study hereditary classes more generally. Perhaps the most famous hereditary class, that has been studied for the past 50 years, is the class of perfect graphs. The class was introduced by Berge in 1961, who was motivated by the study of communication theory. This class inspired an enormous amount of research from different fields. Berge's famous Strong Perfect Graph Conjecture was proved using a decomposition theorem. This decomposition theorem uses cutsets that are fundamentally different from the ones used in the decomposition of minor-closed classes. It is also known that perfect graphs can be recognized in polynomial time. The key open problem in the area is whether it is possible, for perfect graphs, to solve the related optimization problems (clique, stable set, coloring and covering of vertices by cliques) by purely graph-theoretical polynomial time algorithms. (It is known that it can be done indirectly, using the ellipsoid method). Challenging problems like these motivate the proposed research. Solving them will require development of new tools and techniques to study hereditary classes more generally.In the past few decades a number of important results were obtained through use of decomposition, where one gains an understanding of a complex structure by breaking it down into simpler parts. A number of very interesting hereditary classes are now structurally well understood, but for some of them (and in particular those that need cutsets similar to the ones used to decompose perfect graphs) it is still not clear how to exploit their structure algorithmically. This project will focus on the structural and computational study of several appropriately chosen hereditary graph classes, with the aim of gaining the insight into the structure of hereditary classes more generally, and an insight into boundary of what is computationally feasible.