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.