The course will provide an in-depth coverage of all aspects of the possibly two most important graph decompositions, namely tree-decompositions and clique-decompositions, with a focus on the techniques required for the design of efficient decomposition based algorithms. After attending the course the students will have a good understanding of the properties of tree-decompositions and clique-decompositions and an excellent understanding of when and how to apply the decompositional approach to a wide variety of problems in computer science.

Decomposition based approaches to tackle computationally hard problems are an integral part in almost all areas of computer science and come with a wide variety of algorithmic applications. The main idea behind decomposition based techniques is to decompose a problem instance into small tractable parts, and to reassemble the solution of the parts to a solution of the entire instance. The course will provide an in-depth coverage of all aspects of the possibly two most important graph decompositions, namely tree-decompositions and clique-decompositions, with a focus on the techniques required for the design of efficient decomposition based algorithms.

This course requires basic knowledge on the design and analysis of algorithms as well as basic complexity theory. Knowledge of the topics covered in the Algorithmics course is an advantage.