Algorithms for Perfect Graph and Other Hereditary Graph Classes

开发有效的算法来解决优化问题是非常重要的现代技术社会。许多问题出现在不同的领域，如运输，电信，分子生物学，工业工程等，当通过图建模时，简化为诸如找到最大团（其是全部成对相邻的节点的集合）、或稳定集合（其是没有一个节点是成对相邻的节点的集合）、或着色问题（即，使用最小数量的颜色来对图的顶点着色，使得没有两个相邻顶点接收相同的颜色）的大小的问题。不幸的是，这些基本的优化问题一般都是NP难解决的，这意味着不太可能有一种有效的方法来解决它们（即不太可能存在多项式时间算法来解决这些问题）。当限制到特殊的图类时，它们变得多项式可解，但即使在输入图上施加了看似相当多的结构时，它们也仍然很困难。了解结构的原因，使有效的算法，这样的优化problem是主要的兴趣，这proposal.In过去的几十年中，一些重要的结果，通过使用分解理论，其中一个获得的理解，一个复杂的结构，通过分解成简单的部分。例如，著名的强完美图猜想（通过排除诱导子图来刻画完美图，这是从通信理论研究中出现的一类）被分解定理证明。也知道如何使用这个分解定理构造一个多项式时间的识别算法的完美图。目前尚不清楚的是如何利用它来构造相关的优化问题。这个项目将专注于开发技术，把这样的分解定理转化为有效的优化算法。这在处理复杂的遗传图类（如完美图）时特别困难，因为它们的分解需要非常强的割集，并且不清楚如何在所需的算法中使用它们。

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.