Combinatorial Optimization Algorithms for Hereditary Graph Classes

开发有效的算法来解决组合问题已成为现代技术社会的重要组成部分。应用包括不同的领域，如运输，电信，分子生物学，工业工程等。问题，如分配频率的移动的电话，可以使用图建模，然后将问题归结为着色图的顶点，使得没有两个相邻的顶点接收相同的颜色（当然，我们感兴趣的是最小的颜色数，这被称为图的色数）。真实的世界中的许多其他应用都归结为图上的相同着色问题。不幸的是，图的色数的求解以及其他一些优化问题，如图的最大团的大小的求解，一般都是NP-完全的。这意味着这些问题不太可能在计算机上有效地解决（即不太可能存在这些问题的多项式时间算法）。处理这种情况的方法之一是找到可以在多项式时间内解决这些问题的图类。本项目将集中于开发通过对遗传图类进行结构分析来获得组合优化算法的技术。许多重要的图类是遗传的（即在导出子图下是封闭的），例如完美图。对于一个困难的优化问题，例如找到一个图的色数或它的最大团的大小，对于给定的类在多项式时间内是可解的，这意味着这个类必须有一些强结构。拟议的研究是关于试图了解什么是这种强大的结构，将允许多项式时间的组合优化算法，并开发技术，以获得所需的结构定理，并使用它们的算法。

Developing efficient algorithms for solving combinatorial problems has been of great importance to the modern technological society. The applications include diverse areas such as transportation, telecommunication, molecular biology, industrial engineering, etc. Problems such as assigning frequencies to mobile telephones, can be modeled using graphs, and then the problem is reduced to coloring the vertices of the graph so that no two adjacent vertices receive the same color (of course the interest is in the minimum number of colors, and this is called the chromatic number of a graph). Many other applications in the real world reduce to the same coloring problem on graphs. Unfortunately, finding the chromatic number of a graph and some other optimization problems such as finding the size of a largest clique in a graph, are NP-complete in general. This means that it is highly unlikely that these problems can be solved efficiently on a computer (i.e. it is unlikely that polynomial time algorithms for these problems exist). One of the ways to deal with this situation is to find classes of graphs for which these problems can be solved in polynomial time.This project will focus on developing techniques for obtaining combinatorial optimization algorithms by expoliting structural analysis of hereditary graph classes. Many important graph classes are hereditary (i.e. closed under taking induced subgraphs), such as perfect graphs. For a difficult optimization problem, such as finding the chromatic number of a graph or the size of its largest clique, to be solvable in polynomial time for a given class, it means that this class must have some strong structure. The proposed research is about trying to understand what is this strong structure that will allow polynomial time combinatorial optimization algorithms, and developing techniques for obtaining the desired structure theorems and using them in algorithms.