Structure of hereditary graph classes and its algorithmic consequences

Developing efficient algorithms for solving combinatorial optimization problems is of great importance to the modern technological society. Many diverse applications in the real world when modelled by graphs reduce to classical optimization problems such as optimally coloring the vertices of a graph (the chromatic number), or finding the size of a largest clique or a stable set. These problems are unfortunately NP-hard in general, but become polynomially solvable when restricted to different classes of graphs.

This project will focus on developing techniques for obtaining combinatorial optimization algorithms by exploiting structural properties of hereditary graph classes (i.e. classes closed under taking induced subgraphs). For a difficult optimization problem to be solved in polynomial time for a given class, it means that this class must have some strong structure. This research is about understanding structural reasons that enable the design of efficient algorithms, and developing techniques for obtaining the desired structure theorems and using them in algorithms.