Structure of hereditary graph classes and their consequences

点击翻译按钮获取中文摘要

Many important graph-theoretic problems such as minimum vertex colouring, maximum clique, and maximum stable set are NP-complete in general (suggesting that there are likely no polynomial-time algorithms for these problems), but can be solved in polynomial time for certain classes of graphs whose structure can be exploited. For hereditary graph classes (i.e. classes of graphs closed under taking induced subgraphs), we are interested in decomposition theorems: how might we decompose a graph into its basic building blocks such that (1) hard problems can be easily solved on these basic graphs, and (2) the solutions for the basic graphs may be combined to give a solution for the original graph. A simple decomposition theorem where this paradigm works nicely is Dirac's characterisation of chordal graphs, which states that if a graph is chordal then it is either a clique or it has a clique cutset. Possibly the most famous decomposition theorem for hereditary graph classes was published in 2006 by Maria Chudnovsky, Neil Robertson, Paul Seymour and Robin Thomas, which resolved a long-standing conjecture of Claude Berge concerning perfect graphs. In particular, it was shown that a graph G is perfect if and only if G contains neither an odd hole nor an odd antihole as an induced subgraph. This gave way to a polynomial-time recognition algorithm for perfect graphs. It is also known that minimum vertex colouring, maximum clique, and maximum stable set can be solved in polynomial time for perfect graphs. However, this algorithm makes use of the ellipsoid method. It remains open whether it is possible to solve these problems in polynomial time using purely combinatorial methods. This research on perfect graphs opened up many other interesting questions about hereditary graph classes, and for instance motivated the study of even- hole-free graphs; a class which is structurally quite similar to the class of perfect graphs. Although polynomial-time algorithms are known for recognising and finding maximum cliques in even-hole-free graphs, the complexity of finding a maximum stable set and a minimum vertex colouring remain open. Towards a greater understanding of the class of even-hole-free graphs we will consider some of its subclasses and try to understand how their structure can be exploited in algorithms.