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.
The course is losely based on the book "Parameterized Algorithms" by
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh
which is available under:
http://link.springer.com/book/10.1007%2F978-3-319-21275-3
