Structure of Hereditary Graph Classes and Its Algorithmic Consequences

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

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.