Algorithms for Perfect Graph and Other Hereditary Graph Classes

开发求解优化问题的高效算法对现代技术社会具有重要意义。在交通运输、电信、分子生物学、工业工程等不同领域中出现的许多问题，当用图建模时，可以简化为寻找最大集团（即所有节点都是成对相邻的一组节点）或稳定集（即所有节点都不是成对相邻的一组节点）的大小等问题。或者是上色问题（即使用最少数量的颜色为图形的顶点上色，这样相邻的两个顶点的颜色就不会相同）。不幸的是，这些基本的优化问题在一般情况下是np困难的，这意味着不太可能有一个有效的方法来通过计算机解决它们（也就是说，不太可能存在多项式时间算法来解决这些问题）。当它们被限制在特殊的图类中时，它们变得多项式可解，但即使在输入图上施加了看似相当多的结构，它们仍然是困难的。理解结构的原因，使有效的算法，这类优化问题是本提案的主要兴趣。在过去的几十年里，通过使用分解理论获得了许多重要的结果，在分解理论中，人们通过将一个复杂的结构分解成更简单的部分来理解它。例如，著名的强完美图猜想（描述了完美图，一类从通信理论的研究中出现的，通过排除诱导子图）是由分解定理证明的。此外，我们还知道如何利用这个分解定理构造一个多项式时间的完美图识别算法。不知道的是如何利用它来构造相关的优化问题。该项目将重点开发将这些分解定理转化为有效优化算法的技术。这在处理复杂的遗传图类（如完美图）时尤其困难，因为它们的分解需要非常强的切集，并且不清楚如何在期望的算法中使用它们。

Developing efficient algorithms for solving optimization 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). These fundamental optimization problems are unfortunately NP-hard to solve in general, which 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 polynomially solvable when restricted to special graph 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 such optimization problems is the primary interest of this proposal.In the past few decades a number of important results were obtained through the use of decomposition theory, where one gains an understanding of a complex structure by breaking it down into simpler parts. For example, the famous Strong Perfect Graph Conjecture (that characterizes perfect graphs, a class that emerged from the study of communication theory, by excluded induced subgraphs) was proved by a decomposition theorem. Also it is known how to use this decomposition theorem to construct a polynomial time recognition algorithm for perfect graphs. What is not known is how to make use of it for construction of related optimization problems. This project will focus on developing techniques for turning such decomposition theorems into efficient optimization algorithms. This is particularly difficult to do when dealing with complex hereditary graphs classes, such as perfect graphs, because very strong cutsets are needed for their decomposition and it is not clear how to use them in the desired algorithms.