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.

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 beneficiaries 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.

Developing efficient algorithms for solving combinatorial problems has been 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 classical optimization problems addressed in this proposal. Obtaining efficient algorithms for their resolution on hereditary graph classes necessarily involves advancements in their mathematical understanding.

The main thrust of this research is 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 arise in a wide range of applications, there is a real need for this type of theoretical research to continue advancing at the frontier, even though its actual applications will probably not come in the near future.

The results will be disseminated through publications in high quality academic journals, presentations at conferences and workshops, as well as over the WWW. These are the main dissemination routs in this area. With the papers in this field being typically quite long, it usually takes a few years for a paper to go through the refereeing process and appear in a journal. Making preprints of papers available over WWW before they are fully refereed, allows other researchers to promptly follow up on the research ideas developed. The PI and her co-authors have an excellent record of quickly disseminating their results, and this practice will continue.