Combinatorial Optimization Algorithms for Hereditary Graph Classes

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.

The proposed research is in the area of algorithms and complexity, which is a branch of theoretical computer science. The project interfaces with mathematics through combinatorics, and with operations research through combinatorial optimization. The main beneficieries include researchers in these areas. The wider interest for PI's work is evidenced by invitations the PI receives to give plenary talks at theoretical computer science and combinatorics workshops and conferences (see Impact Plan). At this point this research is purely theoretical, it develops techniques to handle problems that are at the edge of what is polynomially solvable. Given that optimization problems addressed in this proposal have a wide range of applications (such as transportation, telecommunication, molecular biology, etc.), there is a real need for this type of theoretical research to continue advancing at the frontier, even though its actual application will probably not come in the near future. The results will be disseminated through publications in high-quality academic conferences and journals, as well as over the WWW. With the papers in this field being typically quite long, it usually takes a few years for a paper that is submitted for publication to a journal to actually be published. So workshops, conferences and WWW (making preprints of papers available to other researchers before they are fully refereed) is the main dissemination route in this area. The PI and her co-authors have an excellent record of quickly disseminating their results, allowing other researchers in the area to promptly follow up on their research ideas, as was best evidenced by the work on the Strong Perfect Graph Conjecture. This practice will continue.