Algorithms for Perfect Graph and Other Hereditary Graph Classes

点击翻译按钮获取中文摘要

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.