Structure of Hereditary Graph Classes and Its Algorithmic Consequences

Developing efficient algorithms for solving combinatorial 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). Unfortunately these fundamental optimization problems, and many others essential for wide spectrum of applications, are NP-hard to solve in general. This 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 polynomial time solvable when restricted to special 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 combinatorial problems on hereditary graph classes (i.e. those closed under vertex deletion) is the primary interest of this proposal.

Robertson and Seymour, in their famous Graph Minors Project, elucidated the structure of graph classes that are closed under vertex deletion, and deletion and contraction of edges (i.e. minor-closed). Their structural characterization had far-reaching algorithmic consequences. The graph classes that appear in applications are not necessarily minor-closed, they are more generally just hereditary. What can be said about their structure? It is unlikely to expect such strong structural results with sweeping algorithmic consequences, as was the case with minor-closed classes. Furthermore, as was already evidenced by the study of several complex hereditary graph classes, the set of tools developed in the study of minor-closed classes does not suffice to study hereditary classes more generally.

Perhaps the most famous hereditary class, that has been studied for the past 50 years, is the class of perfect graphs. The class was introduced by Berge in 1961, who was motivated by the study of communication theory. This class inspired an enormous amount of research from different fields. Berge's famous Strong Perfect Graph Conjecture was proved using a decomposition theorem. This decomposition theorem uses cutsets that are fundamentally different from the ones used in the decomposition of minor-closed classes. It is also known that perfect graphs can be recognized in polynomial time. The key open problem in the area is whether it is possible, for perfect graphs, to solve the related optimization problems (clique, stable set, coloring and covering of vertices by cliques) by purely graph-theoretical polynomial time algorithms. (It is known that it can be done indirectly, using the ellipsoid method). Challenging problems like these motivate the proposed research. Solving them will require development of new tools and techniques to study hereditary classes more generally.

In the past few decades a number of important results were obtained through use of decomposition, where one gains an understanding of a complex structure by breaking it down into simpler parts. A number of very interesting hereditary classes are now structurally well understood, but for some of them (and in particular those that need cutsets similar to the ones used to decompose perfect graphs) it is still not clear how to exploit their structure algorithmically. This project will focus on the structural and computational study of several appropriately chosen hereditary graph classes, with the aim of gaining the insight into the structure of hereditary classes more generally, and an insight into boundary of what is computationally feasible.

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. The three optimization problems that will be intensely studied as part of the proposed research are coloring (which has applications in, for example, frequency assignment in communication networks, scheduling, and memory allocation) and clique and stable set problems (with applications in, for example, bioinformatics, molecular biology, coding theory, computer vision, and scheduling). Obtaining efficient algorithms for these and other problems that will be considered, 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 polynomial time solvable. Given that combinatorial 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 may not come in the near future.

The research in structural graph theory, and in particular with respect to hereditary graph classes, is steadily increasing in the last few decades. This kind of research has numerous algorithmic consequences. The algorithms for some hereditary classes remain of high complexity (O(n^5) and more), but some are quite efficient. It is likely that in the future this area will influence real world applications, especially those where one is in control of the input design.

The results will be disseminated through publications in high quality academic journals, presentations at conferences and workshops, as well as online. The PI also plans to organize a workshop that would bring together researchers in structural graph theory and algorithms. 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 online 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.